「Petrozavodsk Summer 2020」Parity Sort
「Petrozavodsk Summer 2020」Parity Sort

2021 年 01 月 21 日

定义一个排列 PP 上的操作 (t,S)(t,S) 为:

  1. 有两个空序列 AABB
  2. 枚举 Si=1S_i=1 的每个 ii:如果 PiP_i 是偶数,则将其放到 AA 的末尾;否则放到 BB 的末尾;
  3. 如果 t=0t=0 则令 C=ABC=\overline{AB},否则令 C=BAC=\overline{BA}
  4. 枚举 Si=1S_i=1 的每个 ii:将 PiP_i 替换为 CC 的开头元素,删去 CC 的开头元素。

现给定排列 PP,要求使用至多 3030 次如上操作,使 PP 从小到大排序,注意你不需要最小化操作次数。

1n150001\le n\le 15000

题意补充

对于 P={0,4,2,3,6,5,1}P=\{0,4,2,3,6,5,1\} 上的操作 (1,1101101)(1,\texttt{1101101}),有示意图如下

题解

由于 30=2(logn)+130=2\left(\left\lfloor\log n\right\rfloor\right)+1,我们考虑 t=0t=0t=1t=1 的操作交错执行。

首先可以确定最后一次操作前,每个数的位置,如 n=13n=13 的时候,最后一次操作前的 pp 应为:

0 8 2 10 4 12 6 7 1 9 3 11 5

故对于每个数,我们求出此时期望的位置 rkrk,也就是说,现在我们要把每个 pip_i,移动到 rkpirk_{p_i} 的位置上。

考虑从低位到高位,每次把这一位是 11 的数不改变相对顺序地丢到最后面,log\log 次后即可完成排序。

先进行一次 (0,1111)(0,111\ldots 1) 操作后,所有偶数都在奇数前面,我们可以认为是两个序列;把偶数中需要放后面的数和奇数中需要放前面的数执行 t=1t=1 操作即可。但 nn 时可能两侧的数字个数不同,这时候给偶数序列中多丢一个 00 就好了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1.5e5 + 9;
int n, m, t, p[N], rk[N];
string s;
vector<int> a, b, c;
vector<pair<bool, string>> ans;
void apply(bool t, const string &s) {
  a.clear(), b.clear();
  for (int i = 0; i < n; i++)
    if (s[i] == '1') (p[i] & 1 ? b : a).push_back(p[i]);
  if (t) swap(a, b);
  c = a, c.insert(c.end(), b.begin(), b.end());
  reverse(c.begin(), c.end());
  for (int i = 0; i < n; i++)
    if (s[i] == '1') p[i] = c.back(), c.pop_back();
  ans.push_back(make_pair(t, s));
}
void solve() {
  int s00 = ((n + 1) / 2 + 1) / 2, s01 = (n + 1) / 4, s10 = s01, s11 = n / 2 - s10;
  assert(s00 + s01 + s10 + s11 == n);
  for (int i = 0; i < s00; i++) rk[i << 1] = i << 1;
  for (int i = 0; i < s10; i++) rk[(i + s00) << 1] = i << 1 | 1;
  for (int i = 0; i < s01; i++) rk[i << 1 | 1] = (i + s00) << 1;
  for (int i = 0; i < s11; i++) rk[(i + s10) << 1 | 1] = (i + s10) << 1 | 1;
  for (int i = 1; i < n; i += 2) rk[i] = n - 1 - rk[i] + (n & 1);
  for (int k = 0; k < 14; k++) {
    apply(0, string(n, '1'));
    s = string(n, '0');
    int t = 0;
    for (int i = 0; i < n; i++)
      if (p[i] % 2 == 0 && (rk[p[i]] >> k) % 2 == 1) s[i] = '1';
    for (int i = 0; i < n; i++)
      if (p[i] % 2 == 1 && (rk[p[i]] >> k) % 2 == 1) s[i] = '1';
    apply(1, s);
  }
  apply(0, string(n, '1'));
  s = string(n, '0');
  for (int i = 0; i < n; i++)
    if (p[i] != i) s[i] = '1';
  apply(1, s);
  for (int i = 0; i < n; i++) assert(p[i] == i);
}
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> p[i];
  solve();
  cout << ans.size() << endl;
  for (const auto &it : ans) cout << (it.first ? 1 : 0) << " " << it.second << endl;
}

评论

TABLE OF CONTENTS

题意补充