CF2127G2 题解

单个询问几乎没有信息，考虑两个近似排列答案的变化量。

如果没有

i\ne k

的限制，那么询问

q

的每个循环移位答案都不变，因为原本的

q_n

入边贡献必定减少，出边贡献必定增多。

那么加上

i\ne k

的限制，如果我们知道无限制时的答案，那么就能知道

q_k

的出边是否属于

q[k+1,n]

。

不妨取

k=\lfloor \frac n2\rfloor+1

，那么每次询问

q

就能知道每个

i

在

q

中与

p_i

的距离是否

\le n-k

。

那么我们如果构造

\log n

个

q

使得对于每个

i

，所有的

j

每次回答不完全相同。

记

b=q^{-1}

，则对于任意

(x,y)

存在一个

b

使得

[b_y-b_i\le n-k]\ne [b_x-b_i\le n-k]

（减法是

\bmod n

意义下的）。

如果 $n$ 是偶数，我们可以按如下方式构造：初始 $b_{d,i}=i$ ， $\forall i\in[1,\frac n2]$ ，如果 $i-1$ 的第 $d$ 个二进制位是 $1$ 就交换 $b_i,b_{i+n/2}$ ，其中 $d\in[0,6]$ 。

考虑任意的 $(i,x,y)$ ，我们要求存在一个 $d$ 使得 $x\bmod \frac n2,y\bmod \frac n2$ 的第 $d$ 位相同或不同，由于 $\frac n2<2^{6}$ 所以必定存在。
如果 $n$ 是奇数，我们可以按如下方式构造： $b_{d,i}=(i-1)\times 2^d\bmod n+1$ ，其中 $d\le [0,6]$ 。

对于 $(i,x,y)$ ，只要某个 $d$ 满足 $2^d(x-y)\bmod n>\frac n2$ 就一定能得到不同的结果，很显然。

想要知道

q

在无限制下的答案，需要先确定任意一个

p_x=y

。

如果

n

是偶数，设

n=2m

，则询问

[q_1,\dots,q_{m},q_{m+1},\dots q_{2m}]

和

[q_{2m},q_{2m-1},\dots,q_m,q_{m+1},q_{m-1},q_{m-2}\dots q_1]

，此时对于任意

i\ne q_{m+1}

，

i\to p_i

在两个排列中恰有一个产生贡献，除非

i=q_m,p_i=q_{m+1}

。

那么我们固定

q_{m+1}

，枚举

q_m

就能找到

p_x=q_{m+1}

的

x

，具体来说找到两次询问之和

=n

的一个作为

x

即可。

如果

n

是奇数，那么固定

q_n=n

，然后

q_m=1\sim n-1

都不满足的时候则

x=n

，注意此时

q_m=x

时答案之和不一定是

n

，要找和最大的一个作为

x

。

因此可以在

2n

次操作内确定

(x,y)

，然后

7n

次询问还原排列，总次数

2n+n\log_2n

。

时间复杂度

\mathcal O(n^2\log n)

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[105][105],b[105],p[105],q[105],w[105];
int ask() {
	cout<<"?";
	for(int i=1;i<=n;++i) cout<<" "<<q[i];
	cout<<endl;
	int o; cin>>o; return o;
}
void solve() {
	cin>>n;
	int k=n/2+1,x=n,y=k; //find p[x]=y
	cout<<k<<endl;
	for(int i=1,m=n-(n&1),c=0;i<=m;++i) if(i!=k) {
		iota(q+1,q+n+1,1),swap(q[i],q[k-1]);
		int z=ask();
		reverse(q+1,q+m+1),swap(q[k],q[k-1]),z+=ask();
		if(i>1&&z>c) { x=i; break; }
		else if(c>z) { x=1; break; }
		else c=z;
	}
	memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
	iota(p+1,p+n+1,1);
	for(int d=0;d<7;++d) {
		if(~n&1) {
			iota(p+1,p+n+1,1);
			for(int i=1;i<=n/2;++i) if((i-1)>>d&1) swap(p[i],p[i+n/2]);
		}
		for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]|=((p[j]+n-p[i])%n<=n-k)<<d;
		for(int i=1;i<=n;++i) q[p[i]]=i;
		for(int i=1;i<=n;++i) w[q[k]]=ask(),rotate(q+1,q+2,q+n+1);
		int o=w[x]+((p[y]+n-p[x])%n<=n-k);
		for(int i=1;i<=n;++i) b[i]|=(o-w[i])<<d;
		if(n&1) for(int i=1;i<=n;++i) p[i]=(p[i]-1)*2%n+1;
	}
	for(int i=1;i<=n;++i) q[i]=find(a[i]+1,a[i]+n+1,b[i])-a[i];
	cout<<"!";
	for(int i=1;i<=n;++i) cout<<" "<<q[i];
	cout<<endl;
}
signed main() {
	int _; cin>>_;
	while(_--) solve();
	return 0;
}

文章操作

相关推荐

评论

CF2127G2 题解