自动搬运

查看原文

来自洛谷，原作者为

	lmh .

搬运于2025-08-24 23:09:07，当前版本为作者最后更新于2025-01-31 21:52:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不妨假设所有 $a_i$ 和 $a_i+a_j$ 互不相等，数据随机，显然冲突的概率极低。

正解数据范围：$n\ge 5$，两次询问，每次询问不超过 $n-1$ 个点对，所有点对互不相等。

一个想法是第一次问一个菊花，第二次问一个环，但这样只能确定第一个位置的值，以及后面的位置组成的集合。

考虑把环上 $(1,2)$ 的询问和菊花上 $(0,n-1)$ 的询问交换，这样只要我们能够正确地把它们换回来，就能用这个信息唯一确定环上节点的顺序。

正确地把它们换回来的方法也很简单，就是枚举所有可能的方案，首先 $a_0$ 需要是整数，其次后面的部分需要能够正确地连成一个环，最后这个环上需要有相邻的 $(1,2)$ 和 $n-1$。

直接做似乎是 $O(n^4)$ 的，不可接受。然而，第一步的正确概率在 $\frac{1}{n}$ 级别，这样复杂度就优化到了 $O(n^3)$；同时，如果发现连不成环可以在循环中途跳出，因此这个复杂度跑不满。

正确率我不太会算，但数据范围 $n=500,V=10^{18},T=20$，这样的话 $\frac{n^5}{V}$ 级别的错误概率也是可以接受的；同时，在本地用 0x66CCFF 的种子随机了 $2\times 10^5$ 组极限数据全部正确，所以没啥过不去的道理。

#include"kiwi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=507;
ll to[N][N],deg[N],U,V;
unordered_map<ll,ll> mp;
__int128 sA,sB;
vector<ll> game(int n){
	vector<ll> ans(n,0),A,B;
	vector<int> qx(n-1),qy(n-1);
	for (int i=1;i<n-1;++i) qy[i-1]=i;
	qx[n-2]=1;qy[n-2]=2;
	A=ask(qx,qy);
	qy[n-2]=n-1;
	for (int i=1;i<n-2;++i){
		qx[i]=i+1;qy[i]=i+2;
	}
	qy[0]=n-1;
	B=ask(qx,qy);
	sA=sB=0;
//	for (int i=0;i<n-1;++i) cout<<A[i]<<' ';cout<<endl;
//	for (int i=0;i<n-1;++i) cout<<B[i]<<' ';cout<<endl;
	for (int i=0;i<n-1;++i){
		sA+=A[i];sB+=B[i];
	}
	for (int i=0;i<n-1;++i) for (int j=0;j<n-1;++j){
		__int128 sumA=sA-A[i]+B[j],sumB=sB-B[j]+A[i];
		if ((sumB%2==0)&&(sumA-sumB/2)%(n-1)==0){
			ans[0]=(sumA-sumB/2)/(n-1);
//			cout<<i<<' '<<j<<' '<<ans[0]<<endl;
			swap(A[i],B[j]);
//			for (int i=0;i<n-1;++i) cout<<A[i]<<' ';cout<<endl;
//			for (int i=0;i<n-1;++i) cout<<B[i]<<' ';cout<<endl;
			for (int k=1;k<n;++k) deg[k]=0;
			int cnt=0;mp.clear();
			for (int k=0;k<n-1;++k) mp[B[k]]=k;
			bool fl=1;
			for (int o=1;o<n;++o){
				for (int p=o+1;p<n;++p) if (mp.find(A[o-1]+A[p-1]-2*ans[0])!=mp.end()){
					++cnt;
					to[o][deg[o]++]=p;to[p][deg[p]++]=o;
					if (mp[A[o-1]+A[p-1]-2*ans[0]]==j) U=o,V=p;
				}
				if (deg[o]!=2){
					fl=0;break;
				}
			}
			if (!fl){
				swap(A[i],B[j]);continue;
			}
			if ((to[V][0]^to[V][1]^U)==i+1) swap(U,V);
			if ((to[U][0]^to[U][1]^V)!=i+1){
				swap(A[i],B[j]);
				continue;
			}
			ans[n-1]=A[i]-ans[0];
			ans[1]=A[U-1]-ans[0];
			ans[2]=A[V-1]-ans[0];
			for (int i=3;i<n-1;++i){
				U=to[V][0]^to[V][1]^U;swap(U,V);
				ans[i]=A[V-1]-ans[0];
			}
			return ans;
		}
	}
	return vector<ll>(n,-1);
}