首先考虑出在什么情况下在位置 $x$ 上进行 $\texttt{throw x}$ 操作可以确定该位置上的值。设 $f_x$ 表示从 $x$ 开始扔球时会进行的次数。若 $f_{x + 1} = f_{x + 2}$，显然 $f_x = f_{x + 1} + 1$，此时无法确定 $x$ 位置上的值。若 $f_{x + 1} \neq f_{x + 2}$，此时可以确定。具体来说，有：
剩下考虑形如 $f_{x + 1} = f_{x + 2}$，而 $x$ 位置上值未知的情况。由于 $f_x = f_{x + 1} + 1 > f_{x + 1}$，因此 $x - 1$ 位置上的值必定已知。尝试进行 $\texttt{swap x}$ 操作，形成新的关系必定满足 $f_x = f_{x + 1} + 1 = f_{x + 2} + 1$，此时若 $f_{x - 1} + 1 = f_{x + 1}$，则说明原来 $x$ 位置上的值为 $2$，否则为 $1$。
特别的，考虑 $1$ 位置上未知的情况。尝试 $\texttt{swap 1}$ 后进行 $\texttt{throw 2}$ 操作，若 $f_2 = f_3 + 1$，则说明原来 $1$ 位置上的值为 $1$，否则为 $2$。
最后来证明操作数不超过 $\lceil\frac{3n}{2}\rceil$。
证明
如上所述，$\texttt{throw x}$ 在每个位置上操作有且仅有 $1$ 次。若 $f_{x + 1} \neq f_{x + 2}$，则不需要进行 $\texttt{swap x}$ 操作，否则必然有 $f_{x - 1} \neq f_x$。因此 $\texttt{swap x} \le \lceil \frac{n}{2} \rceil$。命题得证。
写的时候需要注意，在 $\texttt{swap x}$ 以后需要更新 $f_{x - 1},f_{x}$ 的值，防止出现错误！！！
代码如下：
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
| #include <bits/stdc++.h>
#define pii pair <int,int>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int query (string op,int x)
{
cout<<op<<" "<<x<<endl;fflush (stdout);
if (op == "throw") return read ();
else return -1;
}
void solve ()
{
int n = read ();
vector <int> ans (n + 1),f (n + 3,0),d (n + 1);
for (int i = n;i;--i)
{
if (f[i + 1] != f[i + 2])
{
f[i] = query ("throw",i);
ans[i] = d[i] = 1 + (f[i] != f[i + 1] + 1);
}
else f[i] = f[i + 1] + 1;
}
for (int i = n;i;--i)
{
if (ans[i])
{
f[i] = f[i + d[i]] + 1;
continue;
}
if (f[i + 1] != f[i + 2])
{
f[i] = query ("throw",i);
ans[i] = d[i] = 1 + (f[i] != f[i + 1] + 1);
continue;
}
f[i] = f[i + 1] + 1;
if (i == 1)
{
int x = query ("swap",1);
if (f[2] + 1 == query ("throw",2)) ans[1] = 1;
else ans[1] = 2;
}
else
{
int x = query ("swap",i - 1);
f[i] = query ("throw",i - 1);
ans[i] = d[i] = 1 + (f[i] == f[i + 1] + 1);
swap (f[i - 1],f[i]);swap (d[i - 1],d[i]);
f[i] = f[i + ans[i]] + 1;
}
}
cout<<"! ";
for (int i = 1;i <= n;++i) cout<<ans[i]<<" \n"[i == n];
fflush (stdout);
}
int main ()
{
int t = read ();
while (t--) solve ();
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
