fork download
copy 
  1. /*
  2. * Author: Geeza
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define ld long double
  8. #define ll long long
  9. #define pb push_back
  10. #define fin(a, n) for(int i = a; i < n; i++)
  11. #define fjn(a, n) for(int j = a; j < n; j++)
  12. #define all(a) a.begin(),a.end()
  13. #define allr(a) a.rbegin(),a.rend()
  14. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  15.  
  16. using namespace std;
  17.  
  18. const double PI = acos(-1);
  19. const int N = 2e6+10, M = 1e3+10;
  20. const ll oo = 0x3f3f3f3f3f3f3f3f;
  21. const int mod = 1e9+7, inf = 1e6;
  22. const ld EPS = 1e-9;
  23.  
  24. string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
  25. int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
  26. int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
  27. char dc[] = {'D', 'L', 'R', 'U'};
  28.  
  29. struct node {
  30.     node * nxt[2];
  31.     int cnt;
  32.     node()
  33.     {
  34.         cnt = 0;
  35.         nxt[0] = nullptr, nxt[1] = nullptr;
  36.     }
  37. };
  38.  
  39. struct Trie {
  40.     node *root;
  41.     int sz;
  42.  
  43.     Trie() {
  44.         root = new node();
  45.         sz = 0;
  46.     }
  47.  
  48.     void insert(ll x) {
  49.         node * cur = root;
  50.         for (ll i = 30; i >= 0; i--) {
  51.             int bit = (x >> i) & 1ll;
  52.             if (!cur->nxt[bit]) cur->nxt[bit] = new node();
  53.             cur = cur->nxt[bit];
  54.             cur->cnt++;
  55.         }
  56.         sz++;
  57.     }
  58.  
  59.     void remove(ll x) {
  60.         node * cur = root;
  61.         for (ll i = 30; i >= 0; i--) {
  62.             int bit = (x >> i) & 1ll;
  63.             cur = cur->nxt[bit];
  64.             cur->cnt--;
  65.         }
  66.         sz--;
  67.     }
  68.  
  69.     ll query(ll x) {
  70.         node * cur = root;
  71.         ll ret = 0;
  72.         for (ll i = 30; i >= 0; i--) {
  73.             int bit = (x >> i) & 1ll;
  74.             if (cur->nxt[bit ^ 1] != nullptr && cur->nxt[bit ^ 1]->cnt) {
  75.                 ret |= (1ll << i);
  76.                 cur = cur->nxt[bit^1];
  77.             }
  78.             else cur = cur->nxt[bit];
  79.         }
  80.         return ret;
  81.     }
  82. };
  83.  
  84. void solve() {
  85.     ll n; cin >> n;
  86.     vector<ll> v(n);
  87.     fin(0, n) cin >> v[i];
  88.     vector<ll> pre(n, 0), suff(n, 0);
  89.     pre[0] = v[0];
  90.     fin(1, n) pre[i] = pre[i-1]^v[i];
  91.     suff[n-1] = v[n-1];
  92.     for (int i = n-2; i >= 0; i--) suff[i] = suff[i+1] ^ v[i];
  93.  
  94.     Trie tr;
  95.     tr.insert(0);
  96.  
  97.     ll ans = 0;
  98.     fin(0, n) {
  99.         tr.insert(pre[i]);
  100.         for (int j = i+1; j < n; j++) {
  101.             ans = max(ans, tr.query(suff[j]));
  102.         }
  103.     }
  104.     cout << ans << "\n";
  105. }
  106.  
  107. int main() {
  108.     FAST;
  109. #ifndef ONLINE_JUDGE
  110.     freopen("input.txt","r",stdin);
  111.     freopen("output.txt","w",stdout);
  112. #endif
  113.     int tt = 1; //cin >> tt;
  114.     while(tt--){
  115.         solve();
  116.     }
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gN9Fmt
language:
C++ (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!