Elimination [第二回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202004-open/tasks/past202004_i

解説

https://atcoder.jp/contests/past202004-open/submissions/12898293

トーナメントでの戦いがあるので、これをシミュレートする問題。
先頭から2つずつ戦わせていくというのをN回繰り返していくと、シミュレートを正しく行うことができる。
勝者を残すというのは、下手に配列を使いまわすよりも、次の配列に分けて追加していくほうがやりやすい。
cur配列に現在勝ち残っているプレイヤーを入れておき、先頭から2つずつ取り出して勝者をnxt配列に入れる。
全部終わったら、cur = nxtとして、またcurに対して同様の操作を行っていけばいい。
自分はcur=nxtの代わりとしてswap(cur,nxt)を使っている。

int N, A[1 << 16];
int ans[1 << 16];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, 1 << N) cin >> A[i];

    vector<int> cur;
    rep(i, 0, 1 << N) cur.push_back(i);

    rep(round, 1, N + 1) {
        int n = cur.size();

        vector<int> nxt;
        rep(i, 0, n / 2) {
            int a = cur[i * 2];
            int b = cur[i * 2 + 1];

            if (A[a] < A[b]) {
                ans[a] = round;
                nxt.push_back(b);
            }
            else {
                ans[b] = round;
                nxt.push_back(a);
            }
        }
        swap(cur, nxt);
    }

    rep(i, 0, 1 << N) {
        if (ans[i] == 0) ans[i] = N;
        printf("%d\n", ans[i]);
    }
}