Cod sursa(job #2333100)

Utilizator PetyAlexandru Peticaru Pety Data 31 ianuarie 2019 18:14:53
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;


ifstream fin ("xormax.in");
ofstream fout ("xormax.out");

struct nod {
  int val;
  nod *next[2];
   nod() {
    val = 0;
    next[0] = next[1] = 0;
  }
};
nod *root= new nod;

int n, v[100002], ans, st , dr;

void baga (int x, int poz) {
  nod *node = root;
  for (int i = 20; i >= 0; i--) {
    int bit;
    if (x & (1 << i))
      bit = 1;
    else
      bit = 0;
    if (!(node -> next[bit]))
      node -> next[bit] = new nod;
    node = node -> next[bit];
  }
  node -> val = poz;
}

int query (int x) {
  nod *node = root;
  for (int i = 20; i >= 0; i--) {
    int bit;
    if (x & (1 << i))
      bit = 1;
    else
      bit = 0;
    if (node -> next[!bit])
      node = node -> next[!bit];
    else
      node = node -> next[bit];
  }
  return node -> val;
}


int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> v[i];
    v[i] ^= v[i - 1];
  }
  ans = v[1];
  st = dr = 1;
  baga(v[1], 1);
  for (int i = 2; i <= n; i++) {
    int t = query(v[i]);
    if ((v[t] ^ v[i]) > ans) {
      ans = (v[t] ^ v[i]);
      st = t + 1;
      dr = i;
    }
    baga(v[i], i);
  }
  fout << ans << " " << st << " " << dr;
  return 0;
}