这里说一种非常简单的单\(log\)方法
显然地，如果在某二进制位上，有一些数字是\(0\)，另一些是\(1\)，那么我们考虑尽量地将这一位相同的数字分到不同的集合中，那么可以建一张图，图上相邻的点不在同一集合内
我们不妨从最高位向最低位考虑，假设初始状态中，所有的数字都在同一个组中。每当同一组中的的数字在这一位同时出现了\(1\)和\(0\)时，我们据此将它分成两组，这个过程形似\(01\)字典树
我们反复地进行这个操作，当所有的组中最多都只有两个数字时，意味着最小值最大时当前位为\(1\)，那么我们便把所有在同一组但不在同一连通块中的数字连边，并回退此次分组操作
最后\(DFS\)跑一遍图即可，可以发现这张图最后会是一个森林，总复杂度\(nlog\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<int>>s,t;
vector<int>emp,e[2000005];
int a[2000005],ans[2000005],f[200005];
bool vis[2000005];
int find(int x){
return f[x]==x?x:find(f[x]);
}
void dfs(int x,int now){
if(vis[x])return;
vis[x]=1;
ans[x]=now;
for(auto u:e[x])
dfs(u,now^1);
}
void solve(){
int n,mx;
scanf("%d",&n);
s.push_back(emp);
mx=n;
for(int i=1;i<=n;i++){
f[i]=i;
s[0].push_back(i);
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=30;i>=0;i--){
t.clear();mx=0;
int now=1<<i;
for(auto j:s){
int flag=1;
for(auto k:j)
if(a[k]&now){
if(flag)t.push_back(emp);
t.back().push_back(k);
flag=0;
}
flag=1;
for(auto k:j)
if(!(a[k]&now)){
if(flag)t.push_back(emp);
t.back().push_back(k);
flag=0;
}
}
for(auto i:t)
mx=max(mx,(int)i.size());
swap(s,t);
if(mx<=2){
for(auto i:s)
if(i.size()==2){
int f1=find(i[0]),f0=find(i[1]);
if(f0==f1)continue;
f[f1]=f0;
e[i[0]].push_back(i[1]);
e[i[1]].push_back(i[0]);
}
swap(s,t);
}
}
for(int i=1;i<=n;i++)
if(!vis[i])dfs(i,1);
for(int i=1;i<=n;i++)
printf("%d",ans[i]);
}
int main(){
int t=1;
//scanf("%d",&t);
while(t--)solve();
return 0;
}