Cod sursa(job #1679072)

Utilizator BrandonChris Luntraru Brandon Data 7 aprilie 2016 17:50:03
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>

using namespace std;

const int MaxN = 100005, StartBitPow = 20, INF = 0x3f3f3f3f;

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

int v[MaxN];
int n, st, ed, max_xor = -INF;

class TrieNode {
  int pos;
  TrieNode *Edg[2];

public:
  TrieNode() {
    Edg[0] = Edg[1] = nullptr;
  }

  void TrieAdd(int val, int val_pos, int bitpow = StartBitPow) {
    if(bitpow < 0) {
      pos = val_pos;
      return;
    }

    int prs = (val & (1 << bitpow)) > 0;

    if(Edg[prs] == nullptr) {
      Edg[prs] = new TrieNode;
    }

    Edg[prs]->TrieAdd(val, val_pos, bitpow - 1);
  }

  int TrieQuery(int val, int bitpow = StartBitPow) {
    if(bitpow < 0) {
      return pos;
    }

    int ngt = (val & (1 << bitpow)) == 0;

    if(Edg[ngt] == nullptr) {
      return Edg[!ngt]->TrieQuery(val, bitpow - 1);
    }

    return Edg[ngt]->TrieQuery(val, bitpow - 1);
  }
};

TrieNode *Rt = new TrieNode;

int main() {
  cin >> n;
  Rt->TrieAdd(0, 0);

  for(int i = 1; i <= n; ++i) {
    cin >> v[i];

    v[i] ^= v[i - 1];
    int best_pos = Rt->TrieQuery(v[i]);
    int best_xor = v[best_pos];

    if((best_xor ^ v[i]) > max_xor) {
      max_xor = (best_xor ^ v[i]);
      st = best_pos + 1;
      ed = i;
    }

    Rt->TrieAdd(v[i], i);
  }

  cout << max_xor << ' ' << st << ' ' << ed << '\n';
  return 0;
}