Cod sursa(job #611094)

Utilizator mihai995mihai995 mihai995 Data 30 august 2011 17:25:40
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
using namespace std;

const int N=1<<23;
int v[N],a[N],poz[N],n,val=-1,st,dr;

ifstream in("xormax.in");
ofstream out("xormax.out");

int search(int x)
{
    int r=0;
    for (int d=1<<20,p=1;d;d>>=1)
        if (!v[2*p+1] || x&d && v[p<<1])
        {
            p<<=1;
            r<<=1;
        }
        else
        {
            p=(p<<1)+1;
            r=(r<<1)+1;
        }
    return poz[r];
}

void push(int x)
{
    for (int d=1<<20,p=1;d;d>>=1)
    {
        v[p]++;
        p<<=1;
        if (x&d)
            p++;
    }
}

int main()
{
    int x;
    in>>n>>a[1];
    push(0);
    for (int i=2;i<=n;i++)
    {
        in>>a[i];
        a[i]^=a[i-1];
        x=search(a[i]);
        if (a[i]^a[x]>val)
        {
            val=a[i]^a[x];
            st=x+1;
            dr=i;
        }
        push(a[i-1]);
        poz[a[i-1]]=i-1;
    }
    out<<val<<" "<<st<<" "<<dr<<"\n";
    return 0;
}