Cod sursa(job #1484810)

Utilizator Tester01tester Tester01 Data 11 septembrie 2015 22:19:36
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 20
#define inf (int)1e6+5
int st;

typedef struct Trie {
           Trie *son[2];
           int start;
           Trie(){
           son[0]=son[1]=NULL;
           start = inf;
           }
        } *Arb;

void Insert(int value, int ss, Trie* Top){
 Trie *node = Top;

 for (int i=MaxSize;i>=0;--i){
    int bit = (value>>i)&1;
    if (!node->son[bit]) node->son[bit] = new Trie;
    node = node->son[bit];
   }
   node->start = ss;
}

int Query(int value, Trie* Top){
  Trie *node = Top;
  int answer=0,bit;
  for (int i=MaxSize;i>=0;--i){
      bit = (value>>i)&1;
      if (node->son[bit^1]) {
                    answer += 1<<i;
                    node = node ->son[!bit];
                   }
           else node = node ->son[bit];
  }
  st = node->start;
  return answer;
}

int XOR_LR = 0, aux,n,pozFin,pozSt,ans=0;
int a[(int)1e6];
int main(void){
  ifstream cin("xormax.in");
  ofstream cout("xormax.out");
  cin>>n;
  Arb TrieD = new Trie();
  Arb TrieS = new Trie();
  Insert(0,0,TrieD);
  for (int i=1;i<=n;++i) {
  cin>>a[i];
  XOR_LR = XOR_LR ^ a[i];
  Insert(XOR_LR,i,TrieD);
  if (ans < Query(XOR_LR,TrieD)) {
      ans = Query(XOR_LR,TrieD);
      pozSt = st+1;
      pozFin = i;
     }
 }
cout<<ans<<" "<<pozSt<<" "<<pozFin<<"\n";
return 0;
}