挺有意思的题。
思路
考虑一个比较自然的做法。
我们每次对于一棵树，我们将它的某一条链抽出来。
这样，我们只需要知道这颗树的所有节点与链底的 \(\text{lca}\)，就可以知道它是属于这条链上哪一个节点的下面。
然后就可以递归处理。
由于交互库不是自适应的。
我们可能可以想到随机一个点。
求出这个点与整颗树的 \(\text{lca}\)。
求出 \(\text{lca}\) 之后，我们一定可以知道这个节点一直到根的链是哪些点，以及他们的父子关系，这个有很多求法，我采用的是按子树大小排序。
这样，我们就已经得到了一个比较优秀的做法。
精细实现后可以做到 \(4700\sim 5000\) 次操作。
但是这个还过不了，因为它的操作次数过于随机，经常会变成 \(4900\sim 5000\)。
我们需要更加好的做法。
考虑什么时候对树的划分最为完全。
一定是一个根到叶子的链可以达到最优的状态。
那么我们不妨将开始随机的点往下跳几步。
具体的：
- 开始随机一个点 \(x\)。
- 对于现在在的点 \(x\)，我们遍历到了 \(i\)。
- 求 \(\text{lca}(x,i)\)。
- 若 \(\text{lca}(x,i)=x\)，那么让 \(x\rightarrow i\)，然后继续遍历。
- 否则直接继续遍历。
这样遍历完所有节点后，一定到了一个叶子节点。
但是你写完之后，会发现你的操作次数变成了 \(5000\sim 6000\)。
思考一下问题在哪里。
我们在往下跳的过程中使用了过多的冗余操作。
我们想要把这些操作也用上。
考虑：
若 \(x\) 为 \(y\) 的子树内一点，\(z\) 为 \(y\) 的子树外一点，那么 \(\text{lca}(y,z)=\text{lca}(x,z)\)。
所以，我们在不断往下跳的过程中，\(\text{lca}\) 其实是同样可以往下继承的。
这样就可以在恰好 \(siz-1\) 次操作找到叶子，并求出 \(\text{lca}\)（随机没用了）。
然后你的操作次数就变成了定值，这个定值基于你的实现。
\(10\) 层是可以做到 \(4608\) 或 \(4480\)（特判三个点）。
复杂度基于实现。
Code
这份代码是 \(4480\) 的。
/*
! 如果没有天赋，那就一直重复
! Created: 2024/06/05 09:10:14
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
// #define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)
inline void JYFILE19();
using i64 = long long;
using PII = pair<int, int>;
bool ST;
const int N = 1100;
const int mod = 998244353;
int n, m, fa[N], sz[N], mp[N][N];
vector<int> to[N];
inline int lca(int x, int y) {
if (mp[x][y]) return mp[x][y];
cout << "? " << x << " " << y << endl;
cin >> mp[x][y];
return mp[y][x] = mp[x][y];
}
inline void upd(int x, int y, int k) {
if (mp[x][y]) return;
mp[x][y] = mp[y][x] = k;
}
inline auto sol(vector<int> all, int las = 0) {
if (all.size() == 0) return 0;
if (all.size() == 1) return all[0];
if (all.size() == 2) return fa[all[0]] = las, all[1];
if (all.size() == 3) {
int x = lca(all[0], all[1]);
for (auto i : all) if (i != x) fa[i] = x;
return x;
}
int x = all[0]; vector<int> res;
for (auto i : all) {
if (lca(i, x) == x) {
for (auto j : all) {
if (i == j) break;
upd(i, j, lca(x, j));
}
x = i;
}
}
for (auto i : all) {
sz[lca(i, x)]++;
res.eb(lca(i, x));
}
sort(res.begin(), res.end(), [&](int x, int y) {
return sz[x] < sz[y];
});
res.erase(unique(res.begin(), res.end()), res.end());
for (int i = 0; i < res.size() - 1; i++)
fa[res[i]] = res[i + 1];
for (auto i : all) {
for (auto j : res) if (i == j) goto ed;
if (lca(i, x) != i) to[lca(i, x)].eb(i);
ed:;
}
for (auto i : res) {
auto nt = to[i];
to[i].clear();
auto x = sol(nt, i);
if (x != i) fa[x] = i;
}
return res.back();
}
signed main() {
JYFILE19();
cin >> n, n = (1 << n) - 1;
vector<int> all;
fill(fa + 1, fa + n + 1, -1);
fro(i, 1, n) all.eb(i), mp[i][i] = i;
sol(all);
cout << "! ";
fro(i, 1, n) cout << fa[i] << " ";
cout << endl;
return 0;
}
bool ED;
inline void JYFILE19() {
// freopen("", "r", stdin);
// freopen("", "w", stdout);
srand(random_device{}());
ios::sync_with_stdio(0), cin.tie(0);
double MIB = fabs((&ED - &ST) / 1048576.), LIM = 32;
// cerr << "MEMORY: " << MIB << endl, assert(MIB <= LIM);
}