Cod sursa(job #1143916)

Utilizator cat_red20Vasile Ioana cat_red20 Data 16 martie 2014 12:28:26
Problema Xor Max Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<fstream>
#include<vector>
using namespace std;
int n,x,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;
        v[poz].ind=ind;
        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];
    }
}

int 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[nod].ind;
            return 0;
        }
        else
        {
            ind=v[v[nod].fii[1-bit]].ind;
            return 1;
        }
    }
    if(v[nod].fii[1-bit]==0)
        return query(x,b-1,v[nod].fii[bit]);
    return (1<<b)+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;
        s=s^x;
        sum=query(s,21,0);
        if(sum>sol)
        {
            sol=sum;
            soli=ind+1;
            solj=i;
        }
        update(s,i);
    }
    fout<<sol<<" "<<soli<<" "<<solj;
    return 0;
}