第二回 アルゴリズム実技検定 I問題

第二回 アルゴリズム実技検定 I問題

完全二分木のトーナメントをシュミレーションすれば良い． \(2^{N}\) 人のトーナメントの試合全体は \(2^{N} * 2\) 個程度なのがポイント． 実際，等比数列の和の公式から \(1 + 2 + 4 + \cdots + 2^{N} = 2^{N+1} - 1\)．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  ll n2 = (1LL << n);

  vll mp(n2);

  vll v(n2); rep(i,n2) { cin >> v[i]; v[i]--; mp[v[i]] = i; }

  vll ans(n2, -1);

  rep(i,n){

    vll old;

    swap(v, old);

    rep(j, old.size() / 2){

      ll x = old[2*j];

      ll y = old[2*j+1];

      v.push_back(max(y, x));

      chmax(ans[mp[x]], i);

      chmax(ans[mp[y]], i);

    }

  }

  rep(i,n2){

    cout << ans[i]+1 << endl;

  }

  return 0;

}