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
|
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int w = 1, a = 0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
return a * w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int>
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
#define MckennaGrace fflush(stdin), fflush(stdout);
const int N = 3030;
int dep[N], n, fa[N], tot;
int Dis (int x, int y) {
printf ("? %d %d", x, y); MckennaGrace
return read();
}
vi cur[N];
int ch[N][2];
inline void add (int u, int v) { if (!ch[u][0]) ch[u][0] = v; else ch[u][1] = v; fa[v] = u;}
int siz[N], bot[N];
void dfs (int u) {
siz[u] = 1, bot[u] = u;
if (ch[u][0]) {
dfs(ch[u][0]); siz[u] += siz[ch[u][0]];
}
if (ch[u][1]) {
dfs(ch[u][1]); siz[u] += siz[ch[u][1]];
if (siz[ch[u][1]] > siz[ch[u][0]]) swap(ch[u][0], ch[u][1]);
}
if (ch[u][0]) bot[u] = bot[ch[u][0]];
}
inline void solve (int u) {
int v = 1, D;
while (dep[v] != dep[u] - 1) {
D = Dis(bot[v], u);
D = (dep[u] + dep[bot[v]] - D) / 2;
while (dep[v] < D) v = ch[v][0];
if (dep[v] == dep[u] - 1) break;
v = ch[v][1];
}
add(v, u);
}
int main() {
n = read();
int mx = 0;
For (i, 2, n) dep[i] = Dis(1, i), cur[dep[i]].pb(i), ckmax(mx, dep[i]);
fa[1] = 1;
for (auto v : cur[1]) add(1, v);
For (i, 2, mx) {
dfs(1);
for (auto u : cur[i]) solve (u);
}
printf ("! ");
For (i, 2, n) printf ("%d ", fa[i]);
MckennaGrace
}
|
