CF2159A MAD Interactive Problem

思路

注意到题目要求在 $3n$ 次查询内得到结果，考虑用 $2n-1$ 次得到 $n$ 个值，再用 $n$ 次得到另外 $n$ 个值，最后刚好 $3n-1$ 次。

具体实现

第一问

我们从第 $1$ 个值开始，到第 $i$ 个值结束，其中 $i$ 是从 $2$ 到 $2n$ 的值，每次将它们之间的所有还未确定的值进行询问得到 $res$ 值。

  • 若 $res$ 等于 $0$ ，说明查询的所有值各不相同
  • 在 $i$ 到了某个值时 $res$ 突然不为 $0$ ,说明新增的这个值等于 $res$

第二问

在第一问中，我们确定了 $n$ 个互不相同的数，考虑将它们提取出来，组成一个序列，且此序列恰好包含了 $1$ 到 $n$ 间的所有值，考虑将剩下还未确定的值枚举，在此序列基础上每次加入一个，则枚举的这个值为 $res$。

证明

第一问

记 $1$ 到 $i$ 中还未确定的值组成的序列为 $D_{i}$。
若询问 $D_{i}$ 的 $res$ 不为 $0$,且询问 $D_{i-1}$ 的 $res$ 为 $0$，
则 $D_{i}$ 中存在两个 $res$,而 $D_{i-1}$ 中存在至多一个 $res$。
所以增加的值一定为 $res$。

第二问

已确定的序列中有 $1$ 到 $n$ 的所有值，再增加一个数一定会使得新序列中存在且仅存在一对相同的值，且增加的数等于这个值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
    }
    template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);read(args...);
    }
    template<typename T>void print(T x){
        if(x<0)x=-x,putchar('-');
        if(x>9)print(x/10);
        putchar((x%10)^48);
    }
}
using namespace std;
using namespace FastIO;
const int N=1000;
int T,n,a[N]; 
vector<int>v;
signed main(){
	read(T);
	while(T--){
		read(n);
		rep(i,1,2*n){
			a[i]=0;
		}
		rep(i,2,2*n){
			v.clear();
			putchar('?');
			putchar(' ');
			rep(j,1,i){
				if(a[j]==0){
					v.emplace_back(j);
				}
			}
			print(v.size());
			putchar(' ');
			fep(i,0,v.size()){
				print(v[i]);
				putchar(' ');
			}
			puts("");
			fflush(stdout);
			int res;
			read(res);
			if(res!=0){
				a[i]=res;
			}
		}
		v.clear();
		rep(i,1,2*n){
			if(a[i]!=0){
				v.emplace_back(i);
			}
		}
		rep(i,1,2*n){
			if(a[i]!=0)continue;
			putchar('?');
			putchar(' ');
			print(v.size()+1);
			putchar(' ');
			fep(j,0,v.size()){
				print(v[j]);
				putchar(' ');
			}
			print(i);puts("");
			fflush(stdout);
			int res;
			read(res);
			a[i]=res;
		}
		putchar('!');
		putchar(' ');
		rep(i,1,2*n){
			print(a[i]);
			putchar(' ');
		}
		puts("");
		fflush(stdout);
	}
}