Ankit_132

D

Nov 3rd, 2023
541
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. struct Node {
  7.   Node * links[2];
  8.  
  9.   bool containsKey(int ind) {
  10.     return (links[ind] != NULL);
  11.   }
  12.   Node * get(int ind) {
  13.     return links[ind];
  14.   }
  15.   void put(int ind, Node * node) {
  16.     links[ind] = node;
  17.   }
  18. };
  19. class Trie {
  20.   private: Node * root;
  21.   public:
  22.     Trie() {
  23.       root = new Node();
  24.     }
  25.  
  26.   public:
  27.     void insert(int num) {
  28.       Node * node = root;
  29.       // cout << num << endl;
  30.       for (int i = 31; i >= 0; i--) {
  31.         int bit = (num >> i) & 1;
  32.         if (!node -> containsKey(bit)) {
  33.           node -> put(bit, new Node());
  34.         }
  35.         node = node -> get(bit);
  36.       }
  37.     }
  38.   public:
  39.     int findMax(int num) {
  40.       Node * node = root;
  41.       int maxNum = 0;
  42.       for (int i = 31; i >= 0; i--) {
  43.         int bit = (num >> i) & 1;
  44.         if (node -> containsKey(!bit)) {
  45.           maxNum = maxNum | (1 << i);
  46.           node = node -> get(!bit);
  47.         } else {
  48.           node = node -> get(bit);
  49.         }
  50.       }
  51.       return maxNum;
  52.     }
  53. };
  54.  
  55. int main()
  56. {
  57.     int n;
  58.     cin>>n;
  59.  
  60.     vector<int> a(n-1);
  61.     for(auto &e: a)     cin>>e;
  62.  
  63.     vector<int> b(n);
  64.     for(int i=1; i<n; i++)
  65.         b[i] = b[i-1] ^ a[i-1];
  66.  
  67.     Trie t;
  68.  
  69.     for(auto e: b)
  70.         t.insert(e);
  71.  
  72.     int x = 0;
  73.     for(int e=0; ; e++)
  74.     {
  75.         int mmax = t.findMax(e);
  76.  
  77.         if(mmax == n-1)
  78.         {
  79.             x = e;
  80.             break;
  81.         }
  82.     }
  83.  
  84.     for(auto &e: b)
  85.         e ^= x;
  86.  
  87.     for(auto e: b)      cout<<e<<" ";
  88.     cout<<"\n";
  89. }
Advertisement
Add Comment
Please, Sign In to add comment