Cod sursa(job #2442604)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 24 iulie 2019 15:39:44
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
// mi am adus aminte ca am 90 din cv motiv dubios
using namespace std;

struct Node {
  Node *son[2];
  Node() {
    son[0] = son[1] = NULL;
  }
  void Insert(int x, int bit = 20) {
    if (bit < 0) {
      return;
    }
    int s = (x & (1 << bit)) != 0;
    if (son[s] == NULL) {
      son[s] = new Node();
    }
    son[s]->Insert(x, bit - 1);
  }
  int Query(int x, int bit = 20) {
    if (bit < 0) {
      return 0;
    }
    int s = 1 ^ ((x & (1 << bit)) != 0);
    if (son[s] != NULL) {
      return ((1 << bit) | son[s]->Query(x, bit - 1));
    } else {
      assert(son[1 ^ s] != NULL);
      return son[1 ^ s]->Query(x, bit - 1);
    }
  }
};

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

  int n; cin >> n;
  Node *root = new Node();
  root->Insert(0);
  vector<int> pref(n + 1);
  int ans = 0, stop = 1;
  for (int i = 1; i <= n; ++i) {
    int x; cin >> x;
    if (i == 1) ans = x;
    pref[i] = pref[i - 1] ^ x;
    int curr = root->Query(pref[i]);
    if (curr > ans) {
      ans = curr;
      stop = i;
    }
    root->Insert(pref[i]);
  }
  assert(stop != -1);
  for (int i = stop - 1; i >= 0; --i) {
    if ((pref[i] ^ pref[stop]) == ans) {
      cout << ans << ' ' << i + 1 << ' ' << stop << endl;
      return 0;
    }
  }
  assert(false);
}