923C - Perfect Security - CodeForces Solution


data structures greedy strings trees *1800

Please click on ads to support us..

C++ Code:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  const long long mxn = 32 * 3e5;
  vector<vector<long long>*> tr(mxn);
  long long n;
  cin >> n;
  vector<long long> a(n);
  for (long long i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<long long> cnt(mxn);
  long long tot = 1;
  auto ins = [&](long long x) {
    long long p = 1;
    ++cnt[p];
    for (long long i = 30; i >= 0; --i) {
      long long b = (x >> i) & 1;
      if (!tr[p]) {
        tr[p] = new vector<long long>(2);
      }
      if (!(*tr[p])[b]) {
        (*tr[p])[b] = ++tot;
      }
      p = (*tr[p])[b];
      ++cnt[p];
    }
    ++cnt[p];
  };
  auto qry = [&](long long x) {
    long long p = 1;
    --cnt[p];
    long long res = 0;
    for (long long i = 30; i >= 0; --i) {
      long long b = (x >> i) & 1;
      if (!tr[p] || cnt[(*tr[p])[b]] <= 0) {
        p = (*tr[p])[!b];
        res += (1 << i);
      } else {
        p = (*tr[p])[b];
      }
      --cnt[p];
    }
    --cnt[p];
    return res;
  };
  for (long long i = 0; i < n; ++i) {
    long long b;
    cin >> b;
    ins(b);
  }
  for (long long i = 0; i < n; ++i) {
    cout << qry(a[i]) << ' ';
  }
  cout << '\n';
  return 0;
}
// CAxLUsqDnJpPQXAQrstkugFNFnVqwRmkpcjdPllHQrSPolOgdBlLCaaBEvtjmwnlRGgdiEHKoqJpbdSdPgDBBnzlGoPPSONjBSwzlqLlsiERiHgHgrEqwwpNgbiGfXoC


Comments

Submit
0 Comments
More Questions

281A - Word Capitalization
1646A - Square Counting
266A - Stones on the Table
61A - Ultra-Fast Mathematician
148A - Insomnia cure
1650A - Deletions of Two Adjacent Letters
1512A - Spy Detected
282A - Bit++
69A - Young Physicist
1651A - Playoff
734A - Anton and Danik
1300B - Assigning to Classes
1647A - Madoka and Math Dad
710A - King Moves
1131A - Sea Battle
118A - String Task
236A - Boy or Girl
271A - Beautiful Year
520B - Two Buttons
231A - Team
479C - Exams
1030A - In Search of an Easy Problem
158A - Next Round
71A - Way Too Long Words
160A - Twins
1A - Theatre Square
1614B - Divan and a New Project
791A - Bear and Big Brother
1452A - Robot Program
344A - Magnets