CF Round #642 D - Constructing the Array - Competitive Programming Library

問題

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

問題文

長さ $n$ の数列 $a$ を考える。最初、 $a_i = 0$ 。

$n$ 回操作してね。ただし、 $i$ 回目の操作では、以下の操作を行う。

$0$ のみを含む、長さが最大の連続部分列を選ぶ。複数ある場合は、最も左のものを選ぶ。

その連続部分列を $[l, r]$ とする。長さが奇数なら、 $a \left[ \frac{l+r}{2} \right]$ を、長さが偶数なら、 $a \left[ \frac{l+r-1}{2} \right]$ を $i$ にする。

制約

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$n$ の総和は $2 \times 10^5$ を超えない

サンプル

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;
}