P8320 『JROI-4』Sunset

本题是一道有趣的交互题。

题目大意

有一个 \(1\sim n(n\le 500)\) 的排列 \(a_i\) 未知。设 \(d_i=\max_{k=1}^i \{a_k\}\) 表示排列 \(a\) 的前缀最大值，有以下两种交互方式：

1. ? 1 i 表示询问 \(d_1\sim d_i\) 中有多少不同的值，即集合 \(\{d_1\sim d_i\}\) 的大小；
2. ? 2 pos 表示将 \(a_{pos}\leftarrow 0\)。

有 \(T\) 组测试数据，每组数据中，你需要在不多于 \(5500\) 次交互的条件下还原出原排列 \(a_i\)。

大体思路

很容易发现，前缀最大值 \(d\) 数组具有单调不减的性质，其图像大致如下图所示：

由于 \(d_x\sim d_n\) 的值均相同，证明 \(x\) 位置上的数就是 \(n\)，否则 \(d\) 会在 \(a_p=n\) 的位置增大。

同时，我们可以发现，\(d\) 数组前 \(i\) 项不同值的个数和 \(d\) 本身的图像趋势是相近的，同样是单调不减的。所以，我们可以二分得到位置 \(x\)，使得 \(x\) 是最大的满足 \(\left\vert\{d_1\sim d_x\}\right\vert=\left\vert\{d_1\sim d_n\}\right\vert\) 的位置。

这样，我们得到了 \(a_x=n\)。然后我们利用操作 \(2\) 将 \(a_x\leftarrow 0\)，重复以上操作求出 \(n-1\sim 1\) 的位置即可。

这样每求一个值的位置，进行的交互次数是 \(\Theta(\log n)\)，总的交互次数为 \(\Theta(n\log n)\)，当 \(n=500\) 时次数约为 \(4500\) 次，大体上足以满足要求。

需要注意的是，交互题输出后需要 fflush(stdout); 清空缓存，并且提交函数型交互题不能使用 inline 式函数。

完整代码

#include 
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair PII;
const int maxn = 505;
namespace IO_ReadWrite {
	#define re register
	#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
	char _buf[1<<21], *p1 = _buf, *p2 = _buf;
	template 
	inline void read(T &x){
		x = 0; re T f=1; re char c = gg;
		while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
		while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
		x *= f;return;
	}
	inline void ReadChar(char &c){
		c = gg;
		while(!isalpha(c)) c = gg;
	}
	template 
	inline void write(T x){
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x/10);
		putchar('0' + x % 10);
	}
	template 
	inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int T, n, a[maxn];
int main () {
	scanf("%d", &T);
	while(T --) {
		memset(a, 0, sizeof a);
		scanf("%d", &n);
		Rep(x, n, 1) {
			printf("? 1 %d\n", n);
			fflush(stdout);
			int mx;
			scanf("%d", &mx);
			int L = 1, R = n, pos = n;
			while(L <= R) {//二分
				int mid = (L + R) >> 1;
				printf("? 1 %d\n", mid);
				fflush(stdout);
				int num;
				scanf("%d", &num);
				if(num >= mx) pos = mid, R = mid - 1;
				else L = mid + 1;
			}
			a[pos] = x;
			printf("? 2 %d\n", pos);
			fflush(stdout);
		}
		printf("!");//输出序列
		rep(i, 1, n) printf(" %d", a[i]);
		printf("\n");
		fflush(stdout);
	}
	
	return 0;
}