Cod sursa(job #2185682)

Utilizator Garen456Paun Tudor Garen456 Data 24 martie 2018 19:13:17
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n,x,s,maxi=-1,st,dr;
struct trie
{
    int poz;
    trie *fiu[2];
    trie()
    { poz=0;
        memset(fiu,0,sizeof(fiu));
    }
};
trie *r=new trie;
trie *prc;

int main()
{
    fin>>n;
     int i,j,sol,q;
    for(i=1;i<=n;++i)
    { fin>>x;
        prc=r;
       for(j=20;j>=0;--j)
       {  if ((1<<j)& s) q=1;
       else q=0;
           if( prc->fiu[ q ] ==NULL )
         prc->fiu[  q ]=new trie;
        prc=prc->fiu[ q ];
        if(j==0)
            prc->poz=i;
       }
       s^=x;

       sol=0; prc=r;
       for(j=20;j>=0;--j)
       {
           if ((1<<j)& s) q=0;
           else q=1;

           if(prc->fiu[q]!=NULL)
           { sol^=(1<<j);
               prc=prc->fiu[q];
           }
           else
           { q=q^1;
               prc=prc->fiu[q];
           }
       }
       if(sol>maxi)
       { maxi=sol;
           dr=i;
           st=prc->poz;
       }
    }
    fout<<maxi<<" "<<st<<" "<<dr;
    return 0;
}