Cod sursa(job #1122671)

Utilizator sebinechitasebi nechita sebinechita Data 25 februarie 2014 19:47:20
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define MAX 100100

int a[MAX];

struct trie{
    int val;
    trie* v[2];
    trie(){
        v[0]=v[1]=0;
        val=0;
    }
};

trie* t=new trie;

int invers(int n)
{
    int x=0;
    int i;
    for(i=0;i<=20;i++)
    {
        x*=2;
        x+=((n&(1<<i))>0);
    }
    return x;
}

void introdu(trie* t, int x, int k)
{

    if(k==21)
        {
            t->val++;
            return;
        }

    if((t->v[x%2])==0)
        t->v[x%2]=new trie;

    introdu(t->v[x&1], x/2, k+1);
}

void cauta(trie *t, int x, int k, int &rez)
{
    if(k==21)
    {
        while(!t->val);
        return;

    }
    if(t->v[x&1])
    {
        rez*=2;
        rez+=(x&1);

        cauta(t->v[x&1], x/2, k+1, rez);
    }
    else
    {
        rez*=2;
        rez+=(1^(x&1));

        cauta(t->v[1^(x&1)], x/2, k+1, rez);
    }
}

int main()
{
    int n, i, x, maxim;
    fin>>n;

    for(i=1;i<=n;i++)
    {
        fin>>x;
        a[i]=x^a[i-1];
    }

    introdu(t, 0, 0);
    maxim=-1;

    int stop=1, start;

    for(i=1;i<=n;i++)
    {
        introdu(t, invers(a[i]), 0);
        int rez=0;
        cauta(t, ((1<<21)-1)^invers(a[i]), 0, rez);
        rez=rez^a[i];
        if(rez>maxim)
        {
            stop=i;
            start=rez^a[i];
            maxim=rez;
        }
    }

    for(i=stop-1;;i--)
    {
        if(a[i]==start)
        {
            start=i;
            break;
        }
    }
    fout<<maxim<<" "<<start+1<<" "<<stop<<"\n";
    cout<<(1<<20);
}