Advertisement
ivnikkk

Untitled

Aug 27th, 2022 (edited)
1,074
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  6. typedef long double ld;
  7. #define int long long
  8. pair<bool, pair<vector<pair<int, int>>, vector<pair<int, int>>>> ok(vector<pair<int, int>>& b, int bit) {
  9.     int cnt[2][2] = {};
  10.     vector<pair<int, int>> bit1, bit0;
  11.     for (int i = 0; i < (int)b.size(); i++) {
  12.         cnt[(b[i].first >> bit) & 1ll][b[i].second]++;
  13.         int bt = (b[i].first >> bit) & 1ll;
  14.         if (bt && b[i].second == 1 || !bt && b[i].second == 0) {
  15.             bit1.push_back(b[i]);
  16.         }
  17.         else {
  18.             bit0.push_back(b[i]);
  19.         }
  20.     }
  21.     if (cnt[0][0] == cnt[1][1] && cnt[1][0] == cnt[0][1]) {
  22.         return { true, {bit1, bit0} };
  23.     }
  24.     else {
  25.         return { false, {{},{}} };
  26.     }
  27. }
  28. signed main() {
  29. #ifdef _DEBUG
  30.     freopen("input.txt", "r", stdin);
  31.     freopen("output.txt", "w", stdout);
  32. #endif
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.     cout.tie(nullptr);
  36.     int t; cin >> t;
  37.     while (t--) {
  38.         int n;
  39.         cin >> n;
  40.         vector<vector<pair<int, int>>> group(1);
  41.         for (int i = 0; i < n; i++) {
  42.             int x; cin >> x;
  43.             group[0].push_back({ x, 0 });
  44.         }
  45.         for (int i = 0; i < n; i++) {
  46.             int x; cin >> x;
  47.             group[0].push_back({x, 1});
  48.         }
  49.         int ans = 0;
  50.         for (int bit = 31; bit >= 0; bit--) {
  51.             bool psh = true;
  52.             vector<vector<pair<int, int>>> new_group;
  53.             for (auto& i : group) {
  54.                 auto ret = ok(i, bit);
  55.                 if (ret.first == false) {
  56.                     psh = false;
  57.                     break;
  58.                 }
  59.                 if(!ret.second.first.empty())new_group.push_back(ret.second.first);
  60.                 if (!ret.second.second.empty())new_group.push_back(ret.second.second);
  61.             }
  62.             if (psh) {
  63.                 ans |= (1ll << bit);
  64.                 group.swap(new_group);
  65.             }
  66.             new_group.clear();
  67.         }
  68.         cout << ans << '\n';
  69.     }
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement