Cod sursa(job #1143929)

Utilizator cat_red20Vasile Ioana cat_red20 Data 16 martie 2014 12:56:36
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<fstream>
#include<vector>
using namespace std;
int n,x[100001],s,nr,sol,soli,solj,sum,st,ind;
struct nod
{
    int fii[2],ind;
}t;
vector<nod> v;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
void update(int x,int ind)
{
    int bit,poz=0;
    for(int i=21;i>=0;i--)
    {
        bit=(x&(1<<i))!=0;

        if(v[poz].fii[bit]==0)
        {
            t.ind=ind;
            v.push_back(t);
            v[poz].fii[bit]=v.size()-1;
        }
        poz=v[poz].fii[bit];
        v[poz].ind=ind;
    }
}

void query(int x,int b,int nod)
{
    int bit=(x&(1<<b))!=0;
    if(b==0)
    {
        if(v[nod].fii[1-bit]==0)
        {
            ind=v[v[nod].fii[bit]].ind;
            return;
        }
        else
        {
            ind=v[v[nod].fii[1-bit]].ind;
            return;
        }
    }
    if(v[nod].fii[1-bit]==0)
         query(x,b-1,v[nod].fii[bit]);
    else
        query(x,b-1,v[nod].fii[1-bit]);
}


int main()
{
    fin>>n;
    v.push_back(t);
    update(0,0);
    for(int i=1;i<=n;i++)
    {
        fin>>x[i];
        x[i]^=x[i-1];
        query(x[i],21,0);
        if((x[i]^x[ind])>sol)
        {
            sol=x[i]^x[ind];
            soli=ind+1;
            solj=i;
        }
        update(x[i],i);
    }
    fout<<sol<<" "<<soli<<" "<<solj;
    return 0;
}