CF 1815B Sum Graph

題意

互動題：有一個長度為 $n$ 的排列 $p$，和一個 $n$ 個節點 $0$ 條邊的無向圖。有兩種詢問：

1. 給定一個 $x$，對於所有的 $i$ $(1 \le i \le n)$ 使得 $1 \le x - i \le n$，在 $i$ 和 $x - i$ 間加一條邊；
2. 詢問 $p_i$ 和 $p_j$ 的最短路長度。

最多詢問 $2n$ 次，求原排列。最多猜測兩次。

解析

如果能把圖連成一條鏈的話會比較好做。使用 + n 和 + (n+1) 兩次加邊操作把圖連成這樣的鏈：

首先任意選取一個點 $s$，詢問 $s$ 和其他所有點的距離，最遠的那個節點 $t$ 就是鏈的某個端點。然後又詢問 $t$ 和所有其他點的距離，就可以確定排列了。注意到鏈有兩個端點，所以你會得到兩個排列。

void solve() 
{
	int n;
	std::cin >> n;
	
	int successful;
	std::cout << "+ " << n << std::endl;
	std::cin >> successful;
	assert(successful == 1);
	std::cout << "+ " << n + 1 << std::endl;
	std::cin >> successful;
	assert(successful == 1);
	
	std::vector<int> dis0(n);
	dis0[0] = 0;
	for (int i = 1; i < n; i++) {
		std::cout << "? " << 1 << " " << i + 1 << std::endl;
		std::cin >> dis0[i];
	}
	
	int end = std::max_element(dis0.begin(), dis0.end()) - dis0.begin();
	std::vector<int> dis_end(n);
	dis_end[end] = 0;
	for (int i = 0; i < n; i++) {
		if (i == end) continue;
		std::cout << "? " << end + 1 << " " << i + 1 << std::endl;
		std::cin >> dis_end[i];
	}
	
	std::vector<int> p(n);
	std::iota(p.begin(), p.end(), 0);
	std::sort(p.begin(), p.end(), [&dis_end](int a, int b)
		  {
			  return dis_end[a] < dis_end[b];
		  });
	
	{
		std::vector<int> ans(n);
		for (int i = 0, j = n, t = 0; i < j && t < n;) {
			if (t < n) ans[p[t++]] = --j;
			if (t < n) ans[p[t++]] = i++;
		}
		std::cout << "! ";
		for (int i = 0; i < n; i++) {
			std::cout << ans[i] + 1 << " ";
		}
	}
	{
		std::vector<int> ans(n);
		for (int i = 0, j = n, t = n; i < j && t > 0;) {
			if (t > 0) ans[p[--t]] = --j;
			if (t > 0) ans[p[--t]] = i++;
		}
		for (int i = 0; i < n; i++) {
			std::cout << ans[i] + 1 << " ";
		}
		std::cout << std::endl;
	}
	
	std::cin >> successful;
	assert(successful);
}