Cod sursa(job #2014600)

Utilizator Rodik_RodyRodica Vasilescu Rodik_Rody Data 24 august 2017 01:07:57
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<bits/stdc++.h>
using namespace std;

typedef struct trie {
    int poz;
    trie *a[2];
    trie() { memset(a,0,sizeof(a)); poz=0; }
}*Trie;

int i,j,a[100005],b[30],rs,st,dr,n;
Trie root=new trie,aux;

void Insert(int poz) {
    Trie aux=root;
    for(int i=0;i<=21;++i)
    {
      if(!aux->a[b[i]]) aux->a[b[i]]=new trie;
      aux=aux->a[b[i]];
    }
    aux->poz=poz;
}

int main()
{
  ifstream cin("xormax.in");
  ofstream cout("xormax.out");

  cin>>n;
  for(i=1;i<=n;++i)
  {
    cin>>a[i]; a[i]^=a[i-1];

    memset(b,0,sizeof(b));

    for(j=0;j<=21;++j)
    if((1<<j)&a[i]) b[21-j]=1;

    Insert(i);

    for(aux=root,j=0;j<=21;++j)
    if(aux->a[b[j]^1]) aux=aux->a[b[j]^1];
    else aux=aux->a[b[j]];

    if((a[i]^a[aux->poz])>rs) rs=a[i]^a[aux->poz],st=aux->poz+1,dr=i;
  }

  if(!rs) st=1,dr=n;

  cout<<rs<<' '<<st<<' '<<dr<<'\n';

 return 0;
}