Advertisement
Guest User

Untitled

a guest
Mar 28th, 2022
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. //雪花飄飄北風嘯嘯
  2. //天地一片蒼茫
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. #include <ext/rope>
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10. using namespace __gnu_cxx;
  11. #define int long long
  12. #define ll long long
  13. #define ii pair<ll,ll>
  14. #define iii pair<ii,ll>
  15. #define fi first
  16. #define se second
  17. #define endl '\n'
  18. #define debug(x) cout << #x << ": " << x << endl
  19.  
  20. #define pub push_back
  21. #define pob pop_back
  22. #define puf push_front
  23. #define pof pop_front
  24. #define lb lower_bound
  25. #define ub upper_bound
  26.  
  27. #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
  28. #define all(x) (x).begin(),(x).end()
  29. #define sz(x) (int)(x).size()
  30.  
  31. #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
  32. //change less to less_equal for non distinct pbds, but erase will bug
  33.  
  34. mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
  35.  
  36. const int MOD=998244353;
  37.  
  38. #define vi vector<int>
  39. void FST(vi& a, bool inv) {
  40.     for (int n = sz(a), step = 1; step < n; step *= 2) {
  41.         for (int i = 0; i < n; i += 2 * step) rep(j,i,i+step) {
  42.             int &u = a[j], &v = a[j + step]; tie(u, v) = ii((u + v)%MOD, (u - v + MOD)%MOD);
  43.         }
  44.     }
  45. }
  46.  
  47. int n;
  48. int arr[270000];
  49. int brr[270000];
  50.  
  51. vector<int> cand;
  52. int cnt[270000];
  53.  
  54. const int N=17;
  55. unsigned long long mask[N];
  56.  
  57. int conv(int i){
  58.     int res=0;
  59.     rep(x,0,N) res|=__builtin_parityll(i&mask[x])<<x;
  60.     return res;
  61. }
  62.  
  63. void test(){
  64.     rep(x,0,N) mask[x]=rng();
  65.    
  66.     vi cnt1(1<<N,0),cnt2(1<<N,0);
  67.     rep(x,0,n) cnt1[conv(arr[x])]++;
  68.     rep(x,0,n) cnt2[conv(brr[x])]++;
  69.    
  70.     int tot=0;
  71.     rep(x,0,1<<N) tot=(tot+cnt1[x]*cnt1[x])%MOD;
  72.    
  73.     FST(cnt1,false);
  74.     FST(cnt2,false);
  75.     rep(x,0,1<<N) cnt1[x]=(cnt1[x]*cnt2[x])%MOD;
  76.     FST(cnt1,true);
  77.    
  78.     tot=tot*(1<<N)%MOD;
  79.    
  80.     rep(x,0,n) if (cnt1[conv(cand[x])]==tot) cnt[x]++;
  81. }
  82.  
  83. signed main(){
  84.     ios::sync_with_stdio(0);
  85.     cin.tie(0);
  86.     cout.tie(0);
  87.     cin.exceptions(ios::badbit | ios::failbit);
  88.    
  89.     freopen("simple.in","r",stdin);
  90.     freopen("simple.out","w",stdout);
  91.    
  92.     cin>>n;
  93.     rep(x,0,n) cin>>arr[x];
  94.     rep(x,0,n) cin>>brr[x];
  95.    
  96.     rep(x,0,n) cand.pub(arr[x]^brr[0]);
  97.    
  98.     sort(all(cand));
  99.     rep(x,0,n) cnt[x]=0;
  100.    
  101.     int K=10;
  102.     rep(x,0,K) test();
  103.    
  104.     rep(x,0,n) if (cnt[x]==K){
  105.         cout<<cand[x]<<endl;
  106.         return 0;
  107.     }
  108.    
  109.     cout<<"-1"<<endl;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement