Cod sursa(job #2473808)

Utilizator lucametehauDart Monkey lucametehau Data 14 octombrie 2019 12:22:29
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream cin ("xormax.in");
ofstream cout ("xormax.out");

const int BMAX = 21;

struct Trie {
  int ind;
  Trie *fiu[2];
  Trie() {
    memset(fiu, 0, sizeof(fiu));
    ind = 0;
  }
};

Trie *trie;
int n, mx, l, r;

int v[200005];

void insert(Trie *trie, int bit, int ind) {
  if(bit == 0) {
    trie->ind = ind;
    return;
  }
  int buck = ((1 << bit) & v[ind]) > 0;
  if(!trie->fiu[buck])
    trie->fiu[buck] = new Trie;
  insert(trie->fiu[buck], bit - 1, ind);
}

int search(Trie *trie, int bit, int ind) {
  if(bit == 0)
    return trie->ind;
  int buck = ((1 << bit) & v[ind]) > 0;
  if(trie->fiu[1 - buck])
    return search(trie->fiu[1 - buck], bit - 1, ind);
  return search(trie->fiu[buck], bit - 1, ind);
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    v[i] ^= v[i - 1];
  }
  l = r = 1;
  trie = new Trie;
  insert(trie, BMAX, 0);
  for(int i = 1; i <= n; i++) {
    int ind = search(trie, BMAX, i), sXor = v[i] ^ v[ind];
    // cout << ind << " " << sXor << "\n";
    if(sXor > mx) {
      mx = sXor;
      l = ind + 1;
      r = i;
    }
    // cout << l << " - " << r << "\n";
    insert(trie, BMAX, i);
    // cout << " am bagat\n";
  }
  cout << mx << " " << l << " " << r;
  return 0;
}