「Petrozavodsk Summer 2020」Parity Sort

「Petrozavodsk Summer 2020」Parity Sort

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

  1. 有两个空序列 $A$ 和 $B$
  2. 枚举 $i$ 从 $1$ 到 $n$
    • 如果 $S_i=0$,不进行操作
    • 如果 $S_i=1$,如果 $P_i$ 是偶数,则放到 $A$ 的末尾,否则放到 $B$ 的末尾
  3. 如果 $t=0$,$C=\overline{AB}$;否则 $C=\overline{BA}$。
  4. 枚举 $i$ 从 $1$ 到 $n$
    • 如果 $S_i=0$,不进行操作
    • 如果 $S_i=1$,将 $P_i$ 设为 $C$ 的开头元素,删去 $C$ 的开头元素

现给出一个排列 $P$,你需要使用至多 $30$ 次如上操作,使 $P$ 从小到大排序,注意你并不需要最小化操作次数。

$1\le n\le 15000$。

题意补充

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

题解

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

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

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

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

const int N=150009;
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 i=0;i<n;i++)fprintf(stderr,"%d%c",rk[i]," \n"[i+1==n]);
for(int k=0;k<14;k++){
apply(0,string(n,'1'));
s=string(n,'0');
// for(int i=0;i<n;i++)cerr<<p[i]<<" \n"[i+1==n];
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';
// cerr<<s<<endl;
// for(int i=0;i<n;i++)cerr<<rk[p[i]]<<" \n"[i+1==n];
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++)cerr<<p[i]<<" \n"[i+1==n];
for(int i=0;i<n;i++)assert(p[i]==i);
}

int main(){
#ifdef memset0
// freopen("1.in","r",stdin);
freopen("2.in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(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;
}