CF 1815B Sum Graph

标签: cfinteractiveconstructive

题意

交互题:有一个长度为 的排列 ,和一个 个节点 条边的无向图。有两种询问:

  1. 给定一个 ,对于所有的 使得 ,在 间加一条边;
  2. 询问 的最短路长度。

最多询问 次,求原排列。最多猜测两次。

解析

如果能把图连成一条链的话会比较好做。使用 + n+ (n+1) 两次加边操作把图连成这样的链:

+ n 和 + (n+1) 两次操作后的图

首先任意选取一个点 ,询问 和其他所有点的距离,最远的那个节点 就是链的某个端点。然后又询问 和所有其他点的距离,就可以确定排列了。注意到链有两个端点,所以你会得到两个排列。

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);
}