Cod sursa(job #2507330)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 10 decembrie 2019 00:12:14
Problema Xor Max Scor 100
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;
}