$\texttt{Subtask # 1}$ 我们直接手动模拟。首先肯定要进行一次 ? l S p 操作求得 $4$ 的位置。然后发现 $1$ 至 $3$ 中只有 $3$ 除 $4$ 无法整除，这样我们就可以通过 ! x y 操作求得 $3$ 的位置。同理求出 $2$ 的位置，则最后剩下的一个位置就是 $1$ 了。
$\texttt{Subtask # 2-3}$ $m_2$ 很大，所以我们可以只用 ? l S p 操作每次求出 $[1,n]$ 间的最大值，然后不断缩小区间直至 $[1,1]$。
$\texttt{Subtask # 4-6}$ 看到 $m_2$ 的值在 $20$ 以内，便能猜想复杂度与 $2$ 的幂次有关。计算了一下 $2^{15}$ 与 $5 \times 10^4$ 大致接近，故再次联想到二分。于是乎，就有了二分答案的做法。
对于 ! x y 操作，因为一定要保证询问合法，所以一定是建立在排列上的某位已经确定的情况下。那么肯定需要先从 ? l S p 操作中获取一个数以开始询问。我们想要求出 $[1,n]$ 内的排列，可以先用 ? l S p 操作获取 $n$ 的位置，然后可以根据 $n \bmod (\frac{n}{2},n)$ ，其中余数互部不重复的性质用 ! x y 操作求解出 $(\frac{n}{2},n)$ 内所有数的位置。然后继续减半重复操作直到 $n = 1$ 后把最后一个剩下的位置标记为 $1$ 即可。需要注意的是由于 $m_3$ 的限制，所以 ? l S p 操作时的 $l$ 的大小应该为还未被确定的数的个数，而不是草率的赋值为排列的大小。
$\texttt{Subtask # 7}$ 但是由于一开始的 ? l S p 操作，经过计算发现此时代码无法通过最后一个子任务。最简单的方式就是在最后一次二分时特判以减少一次 ? l S p 操作。最后一次二分操作是在 $[1,2]$ 或 $[1,3]$ 的范围时，但因为题中 $n$ 的大小已经确定，所以计算得出只需要特判后者的情况即可。我们仍然用第一个操作中余数互不相同以求出区间中不同的数的性质，发现 $5 \bmod i (1 \le i \le 3)$，恰好余数互不相同，故最少使用两次 ! x y 操作代替原来的 ? l S p 操作求出。
完整代码如下：
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 #include <iostream> #include <vector> using namespace std;const int MAX = 5e4 + 50 ;vector <int > v; int n,a,b,c,x,y,bg;int num[MAX];void work (int r,int mo) int main () cin>>n>>a>>b>>c; if (n == 4 ) { cout<<"? 4 1 2 3 4 4" <<endl;cout.flush (); cin>>x>>y;num[y] = 4 ; for (int i = 1 ;i <= 4 ;++i) { if (num[i]) continue ; cout<<"! " <<y<<" " <<i<<endl;cout.flush (); cin>>x; if (x != 0 ) { num[i] = 3 ,y = i; break ; } } for (int i = 1 ;i <= 4 ;++i) { if (num[i]) continue ; cout<<"! " <<y<<" " <<i<<endl;cout.flush (); cin>>x; if (x != 0 ) num[i] = 2 ,y = 1 ; else num[i] = 1 ,y = 2 ; break ; } for (int i = 1 ;i <= 4 ;++i) { if (num[i]) continue ; num[i] = y; } cout<<"A " ; for (int i = 1 ;i <= 4 ;++i) cout<<num[i]<<" " ; cout<<endl;cout.flush (); return 0 ; } cout<<"? " <<n<<" " ; for (int i = 1 ;i <= n;++i) cout<<i<<" " ; cout<<n<<endl;cout.flush (); cin>>x>>y; num[y] = n; work (n - 1 ,y); cout<<"A " ; for (int i = 1 ;i <= n;++i) cout<<num[i]<<" " ; cout<<endl;cout.flush (); return 0 ; } void work (int r,int mo) if (r == 1 ) { for (int i = 1 ;i <= n;++i) if (!num[i]) num[i] = num[mo] - 1 ; return ; } v.clear (); if (r == 3 ) { for (int i = 1 ;i <= n;++i) if (!num[i]) v.push_back (i); for (int i = 1 ;i <= n;++i) { if (num[i] == 5 ) { bg = i; break ; } } cout<<"! " <<bg<<" " <<v[0 ]<<endl;cout.flush (); cin>>x; if (x == 0 ) num[v[0 ]] = 1 ; if (x == 1 ) num[v[0 ]] = 2 ; if (x == 2 ) num[v[0 ]] = 3 ; cout<<"! " <<bg<<" " <<v[1 ]<<endl;cout.flush (); cin>>y; if (y == 0 ) { num[v[1 ]] = 1 ; if (x == 1 ) num[v[2 ]] = 3 ; else num[v[2 ]] = 2 ; } if (y == 1 ) { num[v[1 ]] = 2 ; if (x == 0 ) num[v[2 ]] = 3 ; else num[v[2 ]] = 1 ; } if (y == 2 ) { num[v[1 ]] = 3 ; if (x == 0 ) num[v[2 ]] = 2 ; else num[v[2 ]] = 1 ; } return ; } int mid = r >> 1 ,cnt = 0 ; for (int i = 1 ;i <= n;++i) if (!num[i]) ++cnt; cout<<"? " <<cnt<<" " ; for (int i = 1 ;i <= n;++i) if (!num[i]) cout<<i<<" " ; cout<<mid + 1 <<endl;cout.flush (); cin>>x; for (int i = 1 ;i <= x;++i) { cin>>y; if (!num[y]) v.push_back (y); } for (int i = 0 ;i < v.size ();++i) { cout<<"! " <<mo<<" " <<v[i]<<endl;cout.flush (); cin>>x; if (x == 0 ) { num[v[i]] = num[mo] - (num[mo] >> 1 ); if (mid + 1 == num[mo] - (num[mo] >> 1 )) y = v[i]; } else { num[v[i]] = num[mo] - x; if (mid + 1 == num[mo] - x) y = v[i]; } } work (mid,y); }
