Cod sursa(job #1747108)

Utilizator Bodo171Bogdan Pop Bodo171 Data 24 august 2016 15:23:21
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include<fstream>
using namespace std;
int arb[(1<<22)+5],i,xorsum,xormax,x,ap[25],start,stop,n,j;
void ins(int lev,int nod)
{
    arb[nod]=i;
    if(lev==0) return;
    ins(lev-1,2*nod+ap[lev-1]);
}
void query(int lev,int nod)
{
    if(lev==0)
        {
            if(xorsum>xormax) {xormax=xorsum;start=arb[nod]+1;stop=i;}
            return;
        }
    if(arb[2*nod+(1^ap[lev-1])]!=0) {xorsum+=(1<<(lev-1));query(lev-1,2*nod+(1^ap[lev-1]));}
    else query(lev-1,2*nod+ap[lev-1]);
}
int main()
{
    ifstream f("xormax.in");
    ofstream g("xormax.out");
    f>>n;
    xormax=-1;
    for(i=1;i<=n;i++)
    {
        f>>x;
        for(j=0;j<=20;j++)
         {
             if(x&(1<<j)) ap[j]++;
             ap[j]%=2;
         }
         xorsum=0;
         ins(21,1);
         query(21,1);
    }
    if(stop<start) start--;
    g<<xormax<<' '<<start<<' '<<stop;
    return 0;
}