交互题还是很难搞呀~

C. Chocolate Bunny(交互,推导)

假 设 a i % a j = x 假设a_i\%a_j=x 假设ai​%aj​=x

a j % a i = y a_j\%a_i=y aj​%ai​=y

其实就能得到一些东西了

假 设 a i > a j 假设a_i>a_j 假设ai​>aj​

那 么 y = a j 那么y=a_j 那么y=aj​

那 么 x < a j 那么x<a_j 那么x<aj​

那 么 x < y 且 a j = y 那么x<y且a_j=y 那么x<y且aj​=y

所 以 , 经 过 ( i , j ) 得 到 x , 经 过 ( j , i ) 得 到 y 所以,经过(i,j)得到x,经过(j,i)得到y 所以,经过(i,j)得到x,经过(j,i)得到y

x 和 y 的 较 大 值 就 是 a i 和 a j 的 较 小 值 x和y的较大值就是a_i和a_j的较小值 x和y的较大值就是ai​和aj​的较小值

比 如 y 比 较 大 , 那 么 通 过 a j % a i = y 比如y比较大,那么通过a_j\%a_i=y 比如y比较大,那么通过aj​%ai​=y

所 以 唯 一 确 定 a j = y 所以唯一确定a_j=y 所以唯一确定aj​=y

综 上 所 诉 , 2 次 操 作 可 以 求 得 两 个 数 中 的 较 小 值 综上所诉,2次操作可以求得两个数中的较小值 综上所诉,2次操作可以求得两个数中的较小值

2 n − 2 次 操 作 得 到 n − 1 个 数 , 剩 下 那 个 是 n ( 因 为 n 永 远 不 会 当 作 较 小 值 求 出 来 ) 2n-2次操作得到n-1个数,剩下那个是n(因为n永远不会当作较小值求出来) 2n−2次操作得到n−1个数,剩下那个是n(因为n永远不会当作较小值求出来)

#include <bits/stdc++.h>
using namespace std;
int a[10009];
void print(int q,int w){
	cout << "? " << q << " " << w << '\n';
}
int main()
{
	int n;
	cin >> n;
	int last=1;
	for(int i=2;i<=n;i++)
	{
		int q,w;
		print(last,i);
		fflush(stdout);
		cin >> q;
		print(i,last);
		fflush(stdout);
		cin >> w;
		if( q<w )	a[i]=w;	//较大值不改变 
		else 	a[last]=q,last=i;
	}
	a[last]=n;
	cout << "! ";
	for(int i=1;i<=n;i++)
		cout << a[i] << " ";
	fflush(stdout);
}