Cod sursa(job #1218786)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 12 august 2014 15:31:38
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<bits/stdc++.h>
#define ch (c[c[0]-y+1])
using namespace std;

struct cell
{
    cell *s[2];
    cell()
    {
        for (int i=0;i<=1;i++) s[i]=0;
    }
};

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

const int NMAX=100005;

int n;
int b[30],c[30],d[30],puteri[50],poz[2500000];
int a[NMAX],sumepart[NMAX];
cell *root=new cell;

inline void CONVERT(int x)
{
    if (!x) return ;
    if (x==1) {c[++c[0]]=1;return ;}
    CONVERT(x>>1);
    c[++c[0]]=x%2;
}

inline void TRANS()
{
    int i;
    d[0]=0;i=1;
    while (i<=25-c[0]) d[++d[0]]=0,i++;
    i=1;
    while (i<=c[0]) d[++d[0]]=c[i++];
    c[0]=d[0];
    for (i=1;i<=c[0];i++) c[i]=d[i];
}

inline void ADAUGA(cell *nod,int y)
{
    if (nod->s[ch]==NULL) nod->s[ch]=new cell;
    if (y>1) ADAUGA(nod->s[ch],y-1);
}

inline void FIND(cell *nod,int y)
{
    if (nod->s[1-ch]!=NULL)
        {
            b[++b[0]]=1-ch;
            if (y>1) FIND(nod->s[1-ch],y-1);
        }
    else
    if (nod->s[ch]!=NULL)

        {
            b[++b[0]]=ch;
            if (y>1) FIND(nod->s[ch],y-1);
        }
}

int main()
{
    int i,j,aux,maxim=0,start=1,stop=1;
    fin>>n;
    puteri[0]=1;
    for (i=1;i<=30;i++) puteri[i]=puteri[i-1]<<1;
    for (i=1;i<=n;i++)
        {
            fin>>a[i];
            sumepart[i]=sumepart[i-1]^a[i];
        }
    maxim=a[1];
    for (i=2;i<=n;i++)
        {
            c[0]=0;poz[sumepart[i-1]]=i-1;
            CONVERT(sumepart[i-1]);
            TRANS();
            ADAUGA(root,c[0]);

            b[0]=c[0]=aux=0;
            CONVERT(sumepart[i]);
            TRANS();
            FIND(root,c[0]);

            aux=0;
            for (j=1;j<=b[0];j++)
                if (b[j]) aux+=puteri[b[0]-j];

            if (maxim<(sumepart[i]^aux))
                {
                    maxim=sumepart[i]^aux;
                    stop=i;
                    start=poz[aux]+1;
                }
        }
    fout<<maxim<<" "<<start<<" "<<stop<<"\n";
    return 0;
}