Advertisement
RaFiN_

prefix xor postfix maximum

Feb 14th, 2019
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.09 KB | None | 0 0
  1.  
  2.  
  3. ll arr[MAX];
  4.  
  5. string binary(ll n)
  6. {
  7.     string s;
  8.     while(n)
  9.     {
  10.         s+=(n%2)+48;
  11.         n/=2;
  12.     }
  13.  
  14.     return s;
  15. }
  16.  
  17. struct node
  18. {
  19.     node *next[2];
  20.     bool endmark;
  21.     node()
  22.     {
  23.         endmark = false;
  24.         next[0] = next[1] = NULL;
  25.     }
  26. }*root;
  27.  
  28. void Insert(string s)
  29. {
  30.     node *curr = root;
  31.     for(int i = 0;i<s.length();i++)
  32.     {
  33.         int id = s[i] - 48;
  34.         if(curr->next[id]==NULL)
  35.         {
  36.             curr->next[id] = new node();
  37.         }
  38.         curr = curr -> next[id];
  39.     }
  40.     curr->endmark = true;
  41. }
  42.  
  43. void del(node* cur)
  44. {
  45.     for (int i = 0; i < 2; i++)
  46.         if (cur->next[i])
  47.             del(cur->next[i]);
  48.  
  49.     delete (cur);
  50. }
  51.  
  52. ll query(string s,ll pk)
  53. {
  54.     ll ans = 0;
  55.     node *curr = root;
  56.     for(int i = 0;i<s.length();i++)
  57.     {
  58.         if(s[i]=='1')
  59.         {
  60.             if(curr->next[0]!=NULL)
  61.             {
  62.                 ans+=(1ll<<pk);
  63.                 curr = curr->next[0];
  64.             }
  65.             else if(curr->next[1]!=NULL)
  66.             {
  67.                 curr = curr->next[1];
  68.             }
  69.             else break;
  70.         }
  71.  
  72.         else
  73.         {
  74.             if(curr->next[1]!=NULL)
  75.             {
  76.                 ans+=(1ll<<pk);
  77.                 curr = curr->next[1];
  78.             }
  79.             else if(curr->next[0]!=NULL)
  80.             {
  81.                 curr = curr->next[0];
  82.             }
  83.             else break;
  84.         }
  85.         pk--;
  86.  
  87.     }
  88.     return ans;
  89. }
  90.  
  91.  
  92. int main()
  93. {
  94.     booster()
  95.     ///read("input.txt");
  96.  
  97.     int n;
  98.     cin>>n;
  99.     root = new node();
  100.     ll x = 0;
  101.     for(int i = 0;i<n;i++)
  102.     {
  103.         cin>>arr[i];
  104.         x = x ^ arr[i];
  105.         string s = binary(x);
  106.         while(s.length()<60)s+='0';
  107.         reverse(all(s));
  108.  
  109.         Insert(s);
  110.     }
  111.     x = 0;ll ans = 0;
  112.  
  113.     for(int i = n-1;i>=0;i--)
  114.     {
  115.         x = x ^ arr[i];
  116.         string s = binary(x);
  117.         while(s.length()<60)s+='0';
  118.         reverse(all(s));
  119.         ans = max(ans,query(s,59));
  120.     }
  121.     cout<<max(ans,x);
  122.     del(root);
  123.  
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement