解题思路

容易发现，你可以根据变化量得知交换的两个数的大小关系。设 $i<j$，$ps_i=\sum\limits_{k=i}^j[a_k<a_i]$，$pb_i=\sum\limits_{k=i}^j[a_k>a_i]$，$ps_j,pb_j$ 同理，则 $\Delta=-ps_i-pb_j+ps_j+pb_i$。若 $a_i<a_j$，则有 $ps_i<ps_j$，$pb_j<pb_i$，那么必有 $\Delta>0$。

但是如果一次操作只能得到两个位置的偏序关系，那么免不了二分，但是操作次数只有 $3n$。那么我们考虑通过把某个位置与一个特殊的值交换来直接得到它的值。容易想到我们可以跟 1 交换。找到 1 的位置是简单的，由于我们需要获取尽量多的信息，故我们再把 1 交换到序列的最后。

考虑顺序还原，即对于所有 $1\le j<i$ 的位置的值全都还原好了。对于 1 的位置 $n$ 和一个位置 $i$ 交换，$\Delta=-ps_i-(n-i+1)+pb_i$。由于是一个排列，所以有 $pb_i=(n-i+1)-ps_i+1$，那么 $\Delta=-2ps_i+1$，则在没确定的中，有 $\frac{-\Delta+1}{2}$ 个数比当前值小，又因为前面的确定的值已知，故可以使用线段树维护还没有确定的值，然后直接线段树二分确定即可。

具体实现

#include <bits/stdc++.h>
// #define filetestin
// #define filetestout
using i64 = long long;
using ui64 = unsigned long long;
using namespace std;
const int N = 1e5 + 5;
int T = 1, n, id[N], a[N], vis[N];
i64 m;
i64 op (int x, int y)
{
	cout << "swap " << x << ' ' << y << '\n';
	fflush (stdout);
	i64 res;
	cin >> res;
	return res;
}

int t[N << 2];
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
void build (int x, int l, int r)
{
	t[x] = r - l + 1;
	if (l == r)
		return;
	build (ls, l, mid);
	build (rs, mid + 1, r);
}
void update (int x, int l, int r, int p)
{
	-- t[x];
	if (l == r)
		return;
	if (p <= mid)
		update (ls, l, mid, p);
	else
		update (rs, mid + 1, r, p);
}
int kth (int x, int l, int r, int k)
{
	if (l == r)
		return l;
	int tmp = t[ls];
	if (k <= tmp)
		return kth (ls, l, mid, k);
	return kth (rs, mid + 1, r, k - tmp);
}
void solve ()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i)
		id[i] = i;
	int pos = 1;
	for (int i = 2; i <= n; ++ i)
	{
		i64 res = op (pos, i), del = res - m;
		swap (id[i], id[pos]);
		if (del > 0)
			pos = i;
		m = res;
	}
	if (pos != n)
	{
		m = op (pos, n);
		swap (id[pos], id[n]);
	}
	for (int i = 1; i <= n; ++ i)
		vis[id[i]] = i;
	build (1, 1, n);
	a[n] = 1;
	update (1, 1, n, 1);
	for (int i = 1; i < n; ++ i)
	{
		i64 res = op (i, n), del = m - res;
		a[i] = kth (1, 1, n, (del - 1) / 2 + 1);
		update (1, 1, n, a[i]);
		op (i, n);
	}
	cout << "answer ";
	for (int i = 1; i <= n; ++ i)
		cout << a[vis[i]] << ' ';
	cout << '\n';
	fflush (stdout);
}
signed main ()
{
	#ifdef filetestin
		freopen (".in", "r", stdin);
	#endif
	#ifdef filetestout
		freopen (".out", "w", stdout);
	#endif
	#ifdef tests
		cin >> T;
	#endif
	while (T --)
		solve ();
	return 0;
}