一行超人

[153D]给出n个数，你需要将n个数分到两个集合，不妨记第一个集合的异或和为X1，第二个为X2。要求X1+X2最大，保证这个前提下X1最大。输出方案。

题解：想起来其实不难。从低到高考虑，如果sum（X1^X2）的第i位为1，那么X1和X2的这一位不用，但加起来肯定是1.而如果sum 的这一位是0，那么两者就可能都是0或者都是1.我们就加入到当前的方程组中判断是否能都是1。能的话就保留这个更改，否则去除这个方程。做了一遍之后我们在考虑X1最大这个条件。如果sum第i位0为1，那么考虑X1这一位能不能是1.具体做法和上面一样了。但是写起来感觉会很蛋疼。。。于是膜拜了status里的代码。

bitset<maxn>f[70],g[70];
int n,m,c[maxn],p[maxn];
ll sum;
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    n=read();
    for1(i,n)
    {
    	ll x=read();sum^=x;
    	for0(j,62)if(x>>j&1)g[j][i]=1;
    }
    for0(w,1)//第一遍把sum位为0的确定能不能X1和X2都为1,第二遍把sum位为1的确定能不能让X1为1.Orz!!! 
     for3(i,62,0)if((sum>>i&1)==w)
     {
     	f[++m]=g[i];f[m][n+1]=1;p[m]=inf;
     	for1(j,m-1)if(f[m][p[j]])f[m]^=f[j];//用上面的结果来消这个方程 
     	for1(j,n)if(f[m][j]){p[m]=j;break;}//该方程第一位为1的位置 
     	if(p[m]>n)m--;//无用方程或者不可能成立的方程 
		else for1(j,m-1)if(f[j][p[m]])f[j]^=f[m]; //把上面的这一位都消掉 
     }
    for1(i,m)c[p[i]]=f[i][n+1];//确定答案，这时候每个方程一定都被消的只剩一个主元了 
    for1(i,n)printf("%d%c",c[i]+1,i==n?'\n':' ');	
    return 0;
}