fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const char *FILE_IN = "simple.in";
  6. const char *FILE_OUT = "simple.out";
  7.  
  8. const int MAX_N = 270000;
  9.  
  10. unordered_map<long long, int> a;
  11. unordered_map<long long, int> b;
  12.  
  13. vector<long long> cnt_a[MAX_N];
  14. vector<long long> cnt_b[MAX_N];
  15.  
  16. vector<pair<int, int> > sz_a;
  17. vector<pair<int, int> > sz_b;
  18.  
  19. long long mem_a[MAX_N];
  20.  
  21. void read_multimap(int n, unordered_map<long long, int> &m) {
  22.   for (int i = 0; i < n; i++) {
  23.     long long x; scanf("%I64d", &x);
  24.     m[x] += 1;
  25.   }
  26. }
  27.  
  28. void create_histogram(int n, const unordered_map<long long, int> &m, vector<long long> cnt_m[]) {
  29.   for (auto p : m) {
  30.     cnt_m[p.second].push_back(p.first);
  31.   }
  32. }
  33.  
  34. vector<pair<int, int> > get_sizes(const vector<long long> cnt_m[]) {
  35.   vector<pair<int, int> > result;
  36.  
  37.   for (int i = 0; i < MAX_N; i++) {
  38.     if (cnt_m[i].size()) {
  39.       result.push_back({i, cnt_m[i].size()});
  40.     }
  41.   }
  42.  
  43.   return result;
  44. }
  45.  
  46. void solve() {
  47.   time_t start = clock();
  48.  
  49.   int n; scanf("%d", &n);
  50.  
  51.   read_multimap(n, a);
  52.   read_multimap(n, b);
  53.  
  54.   create_histogram(n, a, cnt_a);
  55.   create_histogram(n, b, cnt_b);
  56.  
  57.   sz_a = get_sizes(cnt_a);
  58.   sz_b = get_sizes(cnt_b);
  59.  
  60.   if (sz_a != sz_b) {
  61.     cout << -1 << "\n";
  62.     exit(0);
  63.   }
  64.  
  65.   int h = 0;
  66.   for (auto p : a) {
  67.     for (int j = 0; j < p.second; j++) {
  68.       mem_a[h++] = p.first; 
  69.     }
  70.   }
  71.  
  72.   long long result = -1;
  73.   int len = sz_a[0].first;
  74.   for (int i = 1; i < sz_a.size(); i++) {
  75.     if (cnt_a[len].size() > sz_a[i].second) {
  76.       len = sz_a[i].first;
  77.     }
  78.   }
  79.  
  80.   len = sz_a[rand() % sz_a.size()].first;
  81.  
  82.   random_shuffle(mem_a, mem_a + h);
  83.   long long value = mem_a[0];
  84.   len = a[value];
  85.  
  86.   random_shuffle(cnt_b[len].begin(), cnt_b[len].end());
  87.   random_shuffle(sz_a.begin(), sz_a.end());
  88.  
  89.   vector<long long> candidates;
  90.  
  91.   for (int i = 0; i < cnt_b[len].size(); i++) {
  92.     candidates.push_back(value ^ cnt_b[len][i]);
  93.   }  
  94.  
  95.   sort(candidates.begin(), candidates.end());
  96.  
  97.   for (long long x : candidates) {
  98.     if (1.0 * (clock() - start) / CLOCKS_PER_SEC > 1.40) {
  99.       // cout << i << " of " << cnt_b[len].size() << "\n";
  100.       break;
  101.     }
  102.  
  103.     bool flag = true;
  104.     for (int j = 0; j < sz_a.size(); j++) {
  105.       int l = sz_a[j].first;
  106.       int cnt = sz_a[j].second;
  107.       for (int k = 0; k < cnt; k++) {
  108.         auto it = b.find(cnt_a[l][k] ^ x);
  109.         if (it == b.end() || it->second != a[cnt_a[l][k]]) {
  110.           flag = false;
  111.           break;
  112.         }
  113.       }
  114.       if (!flag) {
  115.         break;
  116.       }
  117.     }
  118.  
  119.     if (flag) {
  120.       result = x;
  121.       break;
  122.     }
  123.   }
  124.  
  125.   printf("%I64d\n", result);
  126. }
  127.  
  128. int main() {
  129.   srand(8132);
  130.  
  131. #ifndef PENGUINS
  132.   freopen(FILE_IN, "r", stdin);
  133.   freopen(FILE_OUT, "w", stdout);
  134. #endif
  135.  
  136.   int cases = 1;
  137.   for (int i = 0; i < cases; i++) {
  138.     solve();
  139.   }
  140.  
  141.   return 0;
  142. }
Time limit exceeded #stdin #stdout 5s 11912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GQJJBU
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!