Cod sursa(job #3261262)

Utilizator Radu_VasileRadu Vasile Radu_Vasile Data 4 decembrie 2024 22:42:17
Problema Xor Max Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
const int MAXLOG = 21;
const int MAXN = 100'000;
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int xorp[MAXN + 1];
struct Node{
  int poz;
  Node *next[2];
};
struct Item{
  int val, poz1, poz2;
};
int start;
Node *createNode() {
  Node *node = (Node *)malloc(sizeof(Node));
  node->next[0] = node->next[1] = NULL;
  return node;
}
struct Trie{
  Node *root;
  void createRoot(){
    root = createNode();
  }
  void update( int nr, int poz ) {
    Node *node = root;
    for( int i = MAXLOG; i >= 0; i-- ) {
      int bit = (nr >> i) & 1;
      if( node->next[bit] == NULL ){
        node->next[bit] = createNode();
        node->poz = poz;
      }
      node = node->next[bit];
    }
  }
  int query( int nr ) {
    int rez = 0;
    Node *node = root;
    for( int i = MAXLOG; i >= 0; i-- ) {
      int bit = (nr >> i) & 1;
      if( node->next[bit ^ 1] == NULL ) {
        start = node->poz;
        node = node->next[bit];
        rez += bit * (1 << i);
      } else {
        start = node->poz;
        node = node->next[bit ^ 1];
        rez += (bit ^ 1) * (1 << i);
      }
    }
    return rez;
  }
}trie;
int main() {
  int n, x, mx, poz1, poz2;
  fin >> n;
  for( int i = 1; i <= n; i++ ) {
    fin >> x;
    xorp[i] = xorp[i - 1] ^ x;
  }
  trie.createRoot();
  mx = 0;
  poz1 = poz2 = 0;
  for( int i = 1; i <= n; i++ ) {
    start = 0;
    trie.update(xorp[i], i);
    x = trie.query(xorp[i]);
    start++;
    if((x ^ xorp[i]) > mx || ((x ^ xorp[i]) == mx && start > poz1)){
      mx = (x ^ xorp[i]);
      poz2 = i;
      poz1 = start;
    }

  }
  fout << mx << " " << poz1 << " " << poz2 << "\n";


  return 0;
}