Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Node {
- Node * links[2];
- bool containsKey(int ind) {
- return (links[ind] != NULL);
- }
- Node * get(int ind) {
- return links[ind];
- }
- void put(int ind, Node * node) {
- links[ind] = node;
- }
- };
- class Trie {
- private: Node * root;
- public:
- Trie() {
- root = new Node();
- }
- public:
- void insert(int num) {
- Node * node = root;
- // cout << num << endl;
- for (int i = 31; i >= 0; i--) {
- int bit = (num >> i) & 1;
- if (!node -> containsKey(bit)) {
- node -> put(bit, new Node());
- }
- node = node -> get(bit);
- }
- }
- public:
- int findMax(int num) {
- Node * node = root;
- int maxNum = 0;
- for (int i = 31; i >= 0; i--) {
- int bit = (num >> i) & 1;
- if (node -> containsKey(!bit)) {
- maxNum = maxNum | (1 << i);
- node = node -> get(!bit);
- } else {
- node = node -> get(bit);
- }
- }
- return maxNum;
- }
- };
- int main()
- {
- int n;
- cin>>n;
- vector<int> a(n-1);
- for(auto &e: a) cin>>e;
- vector<int> b(n);
- for(int i=1; i<n; i++)
- b[i] = b[i-1] ^ a[i-1];
- Trie t;
- for(auto e: b)
- t.insert(e);
- int x = 0;
- for(int e=0; ; e++)
- {
- int mmax = t.findMax(e);
- if(mmax == n-1)
- {
- x = e;
- break;
- }
- }
- for(auto &e: b)
- e ^= x;
- for(auto e: b) cout<<e<<" ";
- cout<<"\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment