D. Divide by three, multiply by two

• Quiz
  • https://codeforces.com/problemset/problem/977/D
  • x2か÷3をして作れる列を復元せよ
• AC
  • https://codeforces.com/contest/977/submission/98420443
• 解説
  • 制約には書いていないが、操作を考えると各数字aは1度しか出てこないことが分かる
  • サンプル1を図示するとDAGになっている
  • トポロジカルソートすればよい

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];

    // 存在確認用
    set<ll> se;
    for(ll a : A)se.insert(a);
    
    // value to index
    map<ll,ll> mp;
    rep(i,N){
      ll a = A[i];
      mp[a] = i;
    }

    VV G(N);
    rep(i,N){
      ll a = A[i];
      if(se.count(2*a)){
        ll j = mp[2*a];
        G[i].push_back(j);
      }
      if(a%3==0 && se.count(a/3)){
        ll j = mp[a/3];
        G[i].push_back(j);
      }
    }
    auto result = topological_sort(G);
    VI Ans;
    for(ll i : result) Ans.push_back(A[i]);
    print_vector(Ans);

    return 0;
}

別解：一本道なので

• 始点が分かれば一本道になることが分かる
• 始点になれる点は、他の数字から遷移してこれない、入次数が0のもの。それが1つだけ存在する
• x2, ÷3のどちらかの遷移先が存在知るので、setで存在確認をlogNで行えば間に合う
• AC https://codeforces.com/contest/977/submission/107385062

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    set<ll> se;
    for(ll a : A)se.insert(a);

    ll start=-1;
    for(ll a : A){
      // 左からの矢印が生えていない
      if(a%2==0 && se.count(a/2))continue;
      if(se.count(3*a))continue;
      
      // 上記条件を通らないものがあるならば、それは始点
      start=a;break;
    }

    VI Ans = {start};
    rep(i,N-1){
      ll a = Ans.back();
      if(se.count(2*a)>0){
        Ans.push_back(2*a); continue;
      }
      if(a%3==0 && se.count(a/3)>0){
        Ans.push_back(a/3); continue;
      }
    }

    print_vector(Ans);
    return 0;
}