CF Round #642 D - Constructing the Array


Tags:cpcodeforcesdiv3constructivesort

問題

https://codeforces.com/contest/1353/problem/D

問題文

長さ nn の数列 aa を考える。最初、 ai=0a_i = 0

nn 回操作してね。ただし、ii 回目の操作では、以下の操作を行う。

  1. 00 のみを含む、長さが最大の連続部分列を選ぶ。複数ある場合は、最も左のものを選ぶ。
  2. その連続部分列を [l,r][l, r] とする。長さが奇数なら、 a[l+r2]a \left[ \frac{l+r}{2} \right] を、長さが偶数なら、 a[l+r12]a \left[ \frac{l+r-1}{2} \right]ii にする。

制約

  • 1t1041 \le t \le 10^4
  • 1n2×1051 \le n \le 2 \times 10^5
  • nn の総和は 2×1052 \times 10^5 を超えない

サンプル

6
1
2
3
4
5
6
1
1 2
2 1 3
3 1 2 4
2 4 1 3 5
3 4 1 5 2 6

考察

そのままシミュレーションしてもいいけど、計算量的に厳しそう。

priority_queue を使って、次はどこを埋めるかを管理すれば問題なさそう。
操作を行った中央より左/右の区間を毎回追加すれば OK。

ただ比較関数は自作する必要がある。長さが長いものを優先して、同じなら左側を優先する。

コード

https://codeforces.com/contest/1353/submission/127018991

void solve() {
  int n;
  cin >> n;
  vector<int> a(n, 0);
  auto comp = [](pair<int, int>& a, pair<int, int>& b) {
    ll lenA = (a.second - a.first);
    ll lenB = (b.second - b.first);
    if (lenA != lenB) {
      return lenA < lenB;
    }
    else {
      return a.first > b.first;
    }
  };
  priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq { comp };
  pq.push({ 0, n - 1 });
  ll i = 1;
  while (!pq.empty()) {
    auto [l, r] = pq.top();
    pq.pop();
    ll mid = (l + r) / 2;
    a[mid] = i++;
    if (l != mid) pq.push({ l, mid - 1 });
    if (r != mid) pq.push({ mid + 1, r });
  }

  for (ll x : a) {
    cout << x << " ";
  }
  cout << endl;
}