题解 [email protected]洛谷 | [email protected] 【Chocolate Bunny】

交互题最好玩♂了!(雾)

题意简述:有一个 nn 个数的排列,每次询问 x,yx,y 得到 axmodaya_x\bmod a_y 的值,最多使用 2×n2\times n 次询问,猜出这个序列。


思路:

看到最多 2×n2\times n 次询问,我们想到了什么?凭我们的直觉,这就是明摆着的提示要询问 i,ji,jj,ij,i 啊!那怎么询问呢?

我们知道对于 a<ba\lt bamodb=aa\bmod b=a,可以得到下面结论:

结论(amodb>bmoda)    (a<b)(a\bmod b\gt b\bmod a)\iff (a\lt b)

简单证明:

if a>b then (amodb)<(bmoda)=bif a=b then (amodb)=(bmoda)=0if a<b then (bmoda)<(amodb)=a\begin{aligned} \operatorname{if}\ a\gt b\ &\operatorname{then}\ (a\bmod b)\lt(b\bmod a)=b\\ \operatorname{if}\ a=b\ &\operatorname{then}\ (a\bmod b)=(b\bmod a)=0\\ \operatorname{if}\ a\lt b\ &\operatorname{then}\ (b\bmod a)\lt(a\bmod b)=a \end{aligned}

在知道这个性质之后,我们就可以想到询问的方法:

mamaa1aia_1\sim a_i 中最大的数的下标(大小可根据上面的结论判断),每次询问 ma,ima,ii,mai,ma,判断两个结果哪个更大,更新偏小的那个下标的值及最大数的下标。

最后剩下一个 amaa_{ma} 没有值,由于数列是 1n1\sim n 的一个排列,因此这个最大的数就是 nn

总询问次数 2×n22\times n-2


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;

int n, a[N], ma = 1;

int ask(int x, int y) {
	int _;
	printf("? %d %d\n", x, y);
	fflush(stdout);
	scanf("%d", &_);
	return _;
}

int main() {
	scanf("%d", &n);
	for(int i=2;i<=n;i++) {
		int _1 = ask(ma, i);
		int _2 = ask(i, ma);
		if(_1 > _2) {
			a[ma] = _1;
			ma = i;
		}
		else a[i] = _2;
	}
	a[ma] = n;
	putchar('!');
	for(int i=1;i<=n;i++) printf(" %d", a[i]);
	return 0;
}