fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty