自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 23:15:17，当前版本为作者最后更新于2025-05-26 22:12:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

怎么没人做，写个题解好了。 upd:发完题解一下就有一堆人做了

首先打表发现，只要 $b_i$ 全是偶数就能构造。注意 $n=1$ 要特判。

考虑归纳构造。考虑去掉 $b_{n-1}$。

我们可以做若干次 $b_{n-1} \to b_{n-1} - 2,b_i \to b_i+2 (i<n-1)$ 的操作，直到 $b_{n-1}$ 变为 $0$。

如果此时 $b_i$ 能够做到全是 $4$ 的倍数，把 $b_i\to \dfrac{b_i}{2}$ 递归构造一个方案，然后对于这个子方案，每个 pair $(x,y)$ 可以变成 $(x,y),(x+2^{n-1},y+2^{n-1})$，也可以变成 $(x,x+2^{n-1}),(y,y+2^{n-1})$。把一个第一种变成第二种就可以使得 $n-1$ 多 $2$ 个，$i$ 减少 $2$ 个。

那么能否做到呢？事实上只要保证能把前面每个 $\frac{b_i}{2}$ 是奇数的必须要 $+2$，也就是 $b_{n-1}$ 如果足够大就满足了。

将 $b_i$ 从小到大排序，此时 $b_{n-1}$ 是最大的，且至少有 $\frac{2^{n-1}}{n}$ 级别。对于 $n$ 大的情况就一定能归纳，不能归纳的情况最大的是 2,6,6,6,6,6，暴力找方案即可。

int n;
pii b[maxn];
bool vis[maxn];

namespace br{

int n;
int z[maxn],nd[maxn],lim;
bool ok=0;
vector<vector<pii>>qwq;
void dfs(int u){
	if(ok) return;
	while(vis[u])++u;
	if(u==(1<<n)){
		bool ook=1;
		For(i,0,n-1) ook&=(z[i]==nd[i]);
		if(ook) ok=1;
//		For(i,0,n-1) cout<<z[i]<<" "; cout<<"\n";
		return;
	}
	For(i,0,n-1){
		int v=(u^(1<<i));
		if(!vis[v]){
			vis[u]=vis[v]=1;
			++z[i]; qwq[i].pb({u,v});
			dfs(u+1);
			if(ok) return;
			vis[u]=vis[v]=0;
			--z[i]; qwq[i].pop_back();
		}
	}
}

vector<vector<pii>>brute(vi o){
	vi bs1={2,6,6,6,6,6};
	n=o.size();
	qwq.resize(n);
	if(o==bs1){
		vector<pii>res= {{0,1},{32,33},{16,18},{48,50},{8,10},{40,42},{24,26},{56,58},{2,6},{34,38},{17,21},{49,53},{9,13},{41,45},{4,12},{36,44},{20,28},{52,60},{22,30},{54,62},{3,19},{35,51},{11,27},{43,59},{7,23},{39,55},{14,46},{25,57},{5,37},{29,61},{15,47},{31,63}};
		for(auto [x,y]:res){
			int k=__lg(x^y);
			qwq[k].pb({x,y});
		}
		return qwq;
	}
	For(i,0,n-1) nd[i]=o[i];
	ok=0;
	dfs(0);
//	cout<<"??? "<<ok<<endl;
	return qwq;
}

}

vector<vector<pii>>solve(vector<int>o){
	int n=o.size();
//	cout<<"solve "<<n<<"\n";
//	for(int x:o)cout<<x<<" "; cout<<" \n";
	if(n==1) return br::brute(o);
	vi o2=o;
	int x=o2.back(); o2.pop_back();
	vi dl(n-1);
	For(i,0,n-2) if(o2[i]/2%2==1) o2[i]+=2,dl[i]++,x-=2;
	if(x<0) return br::brute(o);
	o2.back()+=x,dl.back()+=x/2;
	For(i,0,n-2) o2[i]/=2;
	vector<vector<pii>>res(n),pre=solve(o2);
	For(i,0,n-2){
		For(j,0,o2[i]-1){
			if(dl[i]){
				res[n-1].pb({pre[i][j].fi,pre[i][j].fi|(1<<(n-1))});
				res[n-1].pb({pre[i][j].se,pre[i][j].se|(1<<(n-1))});
				--dl[i];
			} 
			else{
				res[i].pb(pre[i][j]);
				res[i].pb({pre[i][j].fi|(1<<(n-1)),pre[i][j].se|(1<<(n-1))});
			}
		}
	}
	return res;
}

void work()
{
	n=read();
	For(i,0,n-1)b[i].fi=read(),b[i].se=i;
	if(n==1){
		puts("0 1");
		exit(0);
	}
	For(i,0,n-1)if(b[i].fi%2==0); else puts("-1"),exit(0);
	sort(b,b+n);
	
	vi o;
	For(i,0,n-1) o.pb(b[i].fi);
	vector<vector<pii>>res=solve(o);
	
	auto trs=[&](int x){
		int y=0;
		For(i,0,n-1)if(x>>i&1)y|=(1<<b[i].se);
		return y;
	};
	for(auto it:res) for(auto [x,y]:it) cout<<trs(x)<<" "<<trs(y)<<endl;
//	dfs(0);
//	for(auto it:s){
//		for(int x:it)cout<<x<<" ";
//		cout<<"\n";
//	}
}

signed main()
{
	int T=1;
	while(T--)work();
	return 0;
}
/*

*/