今天在讨论题目的时候突然想到的，二分答案，建二分图染色。

但谁都看的出边数是N^2,

我突然想到平面图边数最多是2*n-3，猜测二分图也会有边数限制。

然后我就往后找了10个点，建边之后跑二分图染色。

没想到对了？这样做有正确性吗？还是这只是没有被Hack的乱搞？

// LUOGU_RID: 139909886
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,id;
}a[200010];
bool cmp(node x,node y)
{
	return x.x<y.x;
}
int cnt[200010];
vector<int> g[200010];
int n;
int col[200010];
bool color(int x)
{
	for(int to:g[x])
	{
		if(col[to]==-1) 
		{
			col[to]=col[x]^1;
			if(color(to)) 
				return 1;
		}
		else if(col[to]==col[x])
			return 1;
	}
	return 0;
}
bool check(int x)
{
	for(int i=1;i<=n;i++) g[i].clear();
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=min(n,i+10);j++)
			if((a[i].x^a[j].x)<x) 
			{
				g[i].push_back(j);
				g[j].push_back(i);
			}
	memset(col,-1,sizeof(col));
	for(int i=1;i<=n;i++)
		if(col[i]==-1) 
		{
			col[i]=1;
			if(color(i)) 
				return 0;
		}
	return 1;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].x,a[i].id=i;
	if(n==2)
	{
		cout<<10;
		return 0;
	}
	sort(a+1,a+1+n,cmp);
	int l=1,r=(1<<30)-1,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}	
	check(ans);
	for(int i=1;i<=n;i++) cnt[a[i].id]=col[i];
	for(int i=1;i<=n;i++) cout<<cnt[i]; 
	return 0;
}