Cod sursa(job #2014364)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 23 august 2017 15:18:39
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>

const int S = 2;
const int MAX_B = 20;

class Trie {
  public:
    int poz;
    Trie *son[S + 5];

    Trie() {
      poz = -1;
      son[0] = son[1] = NULL;
    }

    void update(int val, int b, int p) {
      if (b == -1) {
        poz = std::max(poz, p);
      } else {
        int bit = (val & (1 << b)) > 0;
        if (son[bit] == NULL)
          son[bit] = new Trie;
        son[bit] -> update(val, b - 1, p);
      }
    }

    std::pair<int, int> query(int val, int b) {
      int ans = 0;
      Trie* aux;
      aux = this;
      for (; b >= 0; --b) {
        int bit = 1 - ((val & (1 << b)) > 0);
        if (aux -> son[bit] == NULL)
          bit = 1 - bit;
        ans = ans + bit * (1 << b);
        aux = aux -> son[bit];
      }

      std::pair<int, int>sol;
      sol = std::make_pair(ans ^ val, aux -> poz);
      return sol;
    }
};

int main() {
  freopen("xormax.in", "r", stdin);
  freopen("xormax.out", "w", stdout);

  int n, s = 0, ans = -1, st, dr;
  scanf("%d", &n);

  Trie* t;
  t = new Trie;
  t -> update(0, MAX_B, 1);

  for (int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    s ^= x;
    std::pair<int, int>aux = t -> query(s, MAX_B);
    if (aux.first > ans) {
      ans = aux.first;
      st = aux.second;
      dr = i;
    }
    t -> update(s, MAX_B, i + 1);
  }

  printf("%d %d %d\n", ans, st, dr);

  return 0;
}