Cod sursa(job #2516179)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 30 decembrie 2019 15:50:59
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
 
const int MAX_N = 100005;
const int BITS = 24;
 
int n;
 
int arr[MAX_N];
int xor_sums[MAX_N];
 
struct Trie {
  int value;
  Trie *child[2];
  Trie() {
    child[0] = child[1] = NULL;
  }
};
 
void insert(Trie *root, int bit, int value) {
  if (bit == - 1) {
    root->value = value;
  } else {
    if (root->child[((1 << bit) & value) > 0] == NULL) {
      root->child[((1 << bit) & value) > 0] = new Trie;
    }
    insert(root->child[((1 << bit) & value) > 0], bit - 1, value);
  }
}
 
int query(Trie *root, int bit, int value) {
  if (bit == - 1) {
    return (root->value ^ value);
  } else {
    if (((1 << bit) & value) > 0) {
      if (root->child[0] == NULL) {
        return query(root->child[1], bit - 1, value);
      } else {
        return query(root->child[0], bit - 1, value);
      }
    } else {
      if (root->child[1] == NULL) {
        return query(root->child[0], bit - 1, value);
      } else {
        return query(root->child[1], bit - 1, value);
      }
    }
  }
}
 
int main() {
  int ans, max, lo, ri;
  Trie *root = new Trie;
  freopen("xormax.in", "r", stdin);
  freopen("xormax.out", "w", stdout);
  std::cin >> n;
  max = - 1;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
    xor_sums[i] = xor_sums[i - 1] ^ arr[i];
    insert(root, BITS, xor_sums[i]);
    ans = query(root, BITS, xor_sums[i]);
    if (ans > max) {
      max = ans;
      ri = i;
    }
  }
  lo = ri;
  while ((xor_sums[ri] ^ xor_sums[lo - 1]) != max) {
    --lo;
  }
  std::cout << max << " " << lo << " " << ri << "\n";
  return 0;
}