fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<stdio.h>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<set>
  9. using namespace std;
  10. set<long long>xp[60];
  11. set<long long>::iterator it;
  12. int n,cnt_list,m;
  13. long long a[1<<18],b[1<<18],list[1<<18],ax,hs[2][1<<18];
  14. long long ans;
  15. bool dvd[1<<18];
  16. int up;
  17. bool dfs(int id)
  18. {
  19. 	if(id<0)
  20. 	    return true;
  21. 	int i,j,s,p,q,pre;
  22.     bool can[2];
  23.    	int num[2][2];
  24.    	memset(can,true,sizeof(can));
  25.     pre=0;
  26. 	for(j=0;j<n;j++)
  27.    	{
  28.    	   if(dvd[j]||j==n-1)
  29.    	   {
  30.    	   	    memset(num,0,sizeof(num));
  31.   	   	    for(s=pre;s<=j;s++)
  32.   	   	    {
  33.     	   	    if(a[s]&(1LL<<id))
  34. 				   num[0][1]++;
  35. 				else
  36. 				   num[0][0]++;
  37. 				if(b[s]&(1LL<<id))
  38. 				   num[1][1]++;
  39. 				else
  40. 				   num[1][0]++;	
  41. 	   	    }
  42. 	   	    if(num[0][0]!=num[1][0])
  43. 	   	        can[0]=false;
  44. 	        if(num[0][0]!=num[1][1])
  45. 	            can[1]=false;
  46.             if(!can[0]&&!can[1])
  47.                 return false;
  48.   	   	    pre=j+1;
  49.    	   }
  50.     }
  51. 	for(i=0;i<=1;i++)
  52.     {
  53.     	if(!can[i])
  54.     	   continue;
  55.     	pre=0;
  56.     	vector<int>vec;
  57. 	    vec.clear();
  58.     	for(j=0;j<n;j++)
  59.     	{
  60. 	    	if(dvd[j]||j==n-1)
  61. 	    	{
  62. 			    cnt_list=0;
  63. 			    for(s=pre;s<=j;s++)
  64. 			    {
  65.     				if(!(a[s]&(1LL<<id)))
  66.     				   list[cnt_list++]=a[s]; 
  67.     			}
  68.     			for(s=pre;s<=j;s++)
  69.     			{
  70. 			    	if(a[s]&(1LL<<id))
  71. 			    	    list[cnt_list++]=a[s];
  72. 			    }
  73. 			    for(s=0;s<cnt_list;s++)
  74. 			       a[s+pre]=list[s];
  75.     			cnt_list=0;
  76.     			if(i==0)
  77.     			{
  78.     				for(s=pre;s<=j;s++)
  79.     				{
  80. 				    	if(!(b[s]&(1LL<<id)))
  81. 				    	  list[cnt_list++]=b[s];
  82. 				    }
  83. 				    for(s=pre;s<=j;s++)
  84. 				    {
  85.     					if(b[s]&(1LL<<id))
  86.     					   list[cnt_list++]=b[s];
  87.     				}
  88. 			    }
  89. 			    else
  90. 			    {
  91.     				for(s=pre;s<=j;s++)
  92.     				{
  93. 				    	if(b[s]&(1LL<<id))
  94. 				    	   list[cnt_list++]=b[s];
  95. 				    }
  96. 				    for(s=pre;s<=j;s++)
  97. 				    {
  98.     					if(!(b[s]&(1LL<<id)))
  99.     				       list[cnt_list++]=b[s];
  100.     				}
  101.     			}
  102.     			for(s=0;s<cnt_list;s++)
  103.     			    b[s+pre]=list[s];
  104.     			for(s=pre;s<=j;s++)
  105.     			{
  106. 			    	if(a[s]&(1LL<<id))
  107. 		    	    {
  108. 		    	    	if(s>pre)
  109. 		    	    	{
  110.     	    		    	dvd[s-1]=true;
  111. 		    	    	    vec.push_back(s-1);
  112. 						}
  113. 						break;
  114.     	    		}
  115. 			    }
  116. 	    		pre=j+1;
  117. 	    	}
  118. 	    }
  119. 	    if(i==1)
  120. 	       ans|=(1LL<<id);
  121.         it=xp[id].find(ans);
  122.         if(it!=xp[id].end())
  123.         {
  124.             if(dfs(id-1))
  125.                return true;
  126.         }
  127. 		if(i==1)
  128.            ans^=(1LL<<id);
  129.         for(j=0;j<vec.size();j++)
  130.             dvd[vec[j]]=false;
  131.     }
  132.     return false;
  133. }
  134. int main()
  135. {
  136. 	int i,j,s,p,q,id;
  137. 	freopen("simple.in","r",stdin);
  138. 	freopen("simple.out","w",stdout);
  139. 	scanf("%d",&n);
  140. 	for(i=0;i<n;i++)
  141. 	    scanf("%I64d",&a[i]);
  142.     for(i=0;i<n;i++)
  143.         scanf("%I64d",&b[i]);
  144.  //   n=1<<18;
  145.    // for(i=0;i<n;i++)
  146.     //{
  147.     //	a[i]=0;
  148.    //  	for(j=0;j<60;j++)
  149.     //	   a[i]=(a[i]<<1LL)+rand()%2;
  150.   //  }
  151.    // long long c=0;
  152.    // for(j=0;j<60;j++)
  153.    // c=(c<<1LL)+rand()%2;
  154.    // for(i=0;i<n;i++)
  155.     //   b[i]=a[i]^c;
  156. 	ax=0;
  157.     for(i=0;i<n;i++)
  158.     {
  159.         ax=max(ax,a[i]);
  160.         ax=max(ax,b[i]);
  161. 	}
  162. 	random_shuffle(a,a+n);
  163. 	for(up=0;(1LL<<up)<=ax;up++);
  164.     for(i=0;i<min(n,9);i++)
  165.     {
  166.     	for(j=0;j<n;j++)
  167.     	{
  168.     		if(i==0)
  169. 	        	hs[0][j]=a[i]^b[j];
  170.     	    else
  171.     	        hs[1][j]=a[i]^b[j];
  172. 		}
  173. 		if(i==0)
  174. 		{
  175. 		   sort(hs[0],hs[0]+n);
  176. 		   m=n;
  177. 		}
  178. 		else
  179.         {
  180.         	sort(hs[1],hs[1]+n);
  181.         	cnt_list=0;
  182.         	p=0;
  183.         	q=0;
  184.         	while(p<m&&q<n)
  185.         	{
  186. 	        	if(hs[0][p]<hs[1][q])
  187. 	        	   p++;
  188.    	            else if(hs[0][p]>hs[1][q])
  189.    	               q++;
  190.                 else
  191.                 {
  192.                 	list[cnt_list++]=hs[0][p];
  193.                 	p++;
  194.                 	q++;
  195.                 }
  196. 	        }
  197. 	        for(p=0;p<cnt_list;p++)
  198. 	            hs[0][p]=list[p];
  199.             m=cnt_list;
  200.         }
  201.     }
  202.     for(i=0;i<up;i++)
  203.         xp[i].clear();
  204.     cnt_list=0;
  205.     for(i=0;i<m;i++)
  206.     {
  207.     	if(cnt_list==0||hs[0][cnt_list-1]<hs[0][i])
  208.     	    hs[0][cnt_list++]=hs[0][i];
  209.     }
  210.     m=cnt_list;
  211.     for(i=0;i<m;i++)
  212.     {
  213.     	long long now=0;
  214.     	for(j=up-1;j>=0;j--)
  215.     	{
  216. 	    	now|=(hs[0][i]&(1LL<<j));
  217. 	    	xp[j].insert(now);
  218. 	    }
  219.     }
  220. 	memset(dvd,false,sizeof(dvd));
  221.     ans=0;
  222.     if(!dfs(up-1))
  223.        puts("-1");
  224. 	else
  225.        printf("%I64d\n",ans);
  226. 	return 0;
  227. }
Success #stdin #stdout 0s 13968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WB3lgE
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!