Cod sursa(job #1484802)

Utilizator Tester01tester Tester01 Data 11 septembrie 2015 21:28:58
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 20

struct Trie {
           Trie *son[2];
           Trie(){
           son[0]=son[1]=NULL;
           }
        }*Top = new Trie;

void Insert(int value){
 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];
   }
}

int Query(int value){
  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];
  }
  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;
 Insert(0);
 for (int i=1;i<=n;++i) {
  cin>>a[i];
  XOR_LR = XOR_LR ^ a[i];

  Insert(XOR_LR);
  if (ans < Query(XOR_LR)) {
      ans = Query(XOR_LR);
      pozFin = i;
     }
 }
cout<<ans<<" ";
 for (int i=pozFin;i>=1;--i){
  ans^=a[i];
  if (!ans) {
      pozSt = i;
      break;
  }
 }
 cout<<pozSt<<" "<<pozFin<<"\n";
return 0;
}