[游戏开发]小游戏叒AK了！

题目

传送门 to luogu

题目背景
今天的比赛又是小游戏 $AK$ 的万千比赛中平淡无奇的一场。

本来他听说最近一个叫 $\mathsf{t}?\mathsf{i}\mathsf{s}\mathsf{t}$ 的白俄罗斯人挺嚣张的，就准备出一道题来震慑他。但是 $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ 还有校董会要开，所以他打消了这个念头，开始准备他的讲稿。

题目描述
校董会上，$\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ 要大家猜他每天都 $AK$ 了几场比赛。已知第 $i$ 天是 $a_i$ 场，一共 $n$ 天，满足 $1?a_i?n$ 且任意两天的 $AK$ 场数不相同。

你只可以问他两种问题（为什么？因为校长就是这么规定的）：

• 询问 $a_x\mathrm{m}\mathrm{o}\mathrm{d}{a}_y$ 的值。注意你必须满足 $a_x>a_y$，否则 $a_x$ 就直接暴露了，不符合 $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ 装弱麻痹对手的原则；
• 询问他有多少天打了不小于 $p$ 场比赛，来评估他对学校管理有多不在乎。也即 { i ?? ∣ ?? a i ? p , ?? i ∈ S } \{i\;|\;a_i\geqslant p,\;i\in S\} {i∣ai??p,i∈S}，其中 $p\in [1,n]$ 为你给定的参数，$S$ 为你给定的集合。注意询问的是至少打 $p$ 场比赛，而 $a_i$ 是 $AK$ 场数。

现在，你可以问 $m_1$ 次 $a_x\mathrm{m}\mathrm{o}\mathrm{d}{a}_y$ 的值，和 $m_2$ 次集合内不小于 $p$ 的数，但是要满足 $\sum |S|?m_3$ 。

请你猜出 $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ 每天的 $AK$ 场数吧！话说我为什么要猜这个？

数据范围与提示
对于一组数据，满足 $n=m_1=m_3=4$ 而 $m_2=1$ 。

对于其余数据，限制最强的满足 $n=m_1=\frac{1}{3}{m}_3=5\times 10^4$ 而 $m_2=15$ 。

思路

发现 $m_2<{\log }_{2}n$，考虑二分？找到了 $\frac{n}{2}$，那么所有 $x>\frac{n}{2}$ 都去取模它便可知晓。

但是我们需要两次 $m_2$ 询问，问 $?\frac{n}{2}$ 和 $?\frac{n}{2}+1$ 的，找到对称差。这样 $m_2=2{\log }_{2}n$，完全过不了。

优化方式我确实没想到。出发点是，$m_1=n$ 则基本上每次 $m_1$ 询问都可以唯一确定一个数。

显然 $x\mathrm{m}\mathrm{o}\mathrm{d}\frac{n}{2}(n?x>\frac{n}{2})$ 是可以的。而你有没有想过反过来，$n\mathrm{m}\mathrm{o}\mathrm{d}x(\frac{n}{2}?x<n)$ 也是可以的？

只要想到这一点，我们可以最初 $m_2$ 询问一次确定 $n$ 的位置，然后 $m_1$ 询问确定了 $[\frac{n}{2},n)$ 的位置，然后以 $\frac{n}{2}$ 作为新的最大值，递归。

这样一来 $m_1=?{\log }_{2}n?+1$，还是稍微多一点，怎么办？

计算一下发现，经过 $m_2=15$ 次询问，$n$ 恰好为 $4$ 。现在我们只有 $m_1$ 询问，可以做吗？

事实上完全可以。因为 $4\mathrm{m}\mathrm{o}\mathrm{d}x(1?x?3)$ 可以找到 $3$（唯一余数为 $1$ 的数字），接下来的一次询问可以确定 $1$ 或者 $2$，那么最后剩一个空位直接填好。

最后计算一下 $m_3$ 。第一次用 $n$ 问出 $n$ 的位置，接下来是 $n+\frac{n}{2}+\frac{n}{4}+?+1=2n$，恰好是 $3n$ 。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int_;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int MaxN = 50005;

int n, m1, m2, m3;
int a[MaxN];
void solve(int m,int loca){
	a[loca] = m; // mark it
	if(m == 1) return ;
	if(m == 2)
		rep(i,1,n) if(!a[i]){
			a[i] = 1; return ;
		}
	if(m == 4){
		rep(i,1,n) if(!a[i]){
			putchar('!'), putchar(' ');
			writeint(loca), putchar(' ');
			writeint(i), putchar('\n');
			fflush(stdout);
			if(readint() == 1){
				a[loca = i] = 3; break;
			}
		}
		int lst = 0;
		rep(i,1,n) if(!a[i]){
			if(lst){
				a[i] = 3-lst; break;
			}
			putchar('!'), putchar(' ');
			writeint(loca), putchar(' ');
			writeint(i), putchar('\n');
			fflush(stdout);
			lst = a[i] = readint()+1;
		}
		return ;
	}

	int p = (m+1)>>1; // boundary
	putchar('?'), putchar(' ');
	writeint(m-1); // except m
	rep(i,1,n) if(!a[i])
		putchar(' '), writeint(i);
	putchar(' '), writeint(p);
	putchar('\n'); fflush(stdout);
	for(int k=readint(); k; --k)
		a[readint()] = p; // put tag

	int id = 0; // next location
	rep(i,1,n) if(a[i] == p){
		putchar('!'), putchar(' ');
		writeint(loca), putchar(' ');
		writeint(i), putchar('\n');
		fflush(stdout);
		a[i] = m-readint();	
		if(a[i] == m) a[i] = p;
		if(a[i] == p) id = i;
	}

	solve(p,id); // remaining
}

int main(){
	n = readint(), m1 = readint();
	m2 = readint(), m3 = readint();
	printf("? %d ",n);
	rep(i,1,n) writeint(i), putchar(' ');
	writeint(n), putchar('\n');
	fflush(stdout); readint(); // count = 1
	solve(n,readint()), putchar('A');
	rep(i,1,n) putchar(' '), writeint(a[i]);
	putchar('\n'); fflush(stdout);
	return 0;
}