Cod sursa(job #215280)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 18 octombrie 2008 11:58:15
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>

int v[2000000][3], p[3000000], n, i, j, k, l[200000], c[200000][23], a, b, m, o, r[23], t;

void trie(int x, int y)
{
    if(x<21)
    {
        if(v[y][c[i][x]]==0)
        {
            k++;
            v[y][c[i][x]]=k;
        }
        trie(x+1, v[y][c[i][x]]);
    }
    else
    {
        p[y]=i;
    }
}

void caut(int x, int y)
{
    if(x<21)
    {
        if(c[i+1][x]==0)
        {
            if(v[y][1]>0)
            {
                r[x]=1;
                caut(x+1, v[y][1]);
            }
            else
            {
                r[x]=0;
                caut(x+1, v[y][0]);
            }
        }
        else
        {
            if(v[y][0]>0)
            {
                r[x]=1;
                caut(x+1, v[y][0]);
            }
            else
            {
                r[x]=0;
                caut(x+1, v[y][1]);
            }
        }
    }
    else
    {
        o=p[y]+1;
    }
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &l[i]);
        l[i]=l[i]^l[i-1];
        o=l[i];
        for(j=20; j>=0; j--)
        {
            c[i][j]=o%2;
            o=o/2;
        }
    }
    for(i=0; i<=20; i++)
    v[0][i]=0;
    m=l[1];
    a=1;
    b=1;
    for(i=0; i<n; i++)
    {
        trie(0,0);
  //      for(j=0; j<=k; j++)
   //     {
    //        printf("%d %d %d\n", j, v[j][0], v[j][1]);
     //   }
        caut(0,0);
        t=0;
        for(j=0; j<=20; j++)
        {
       //     printf("%d ", r[j]);
            t=t*2+r[j];
        }
      //  printf("\n");
        if(t>m)
        {
            m=t;
            a=o;
            b=i+1;
        }
    }
    printf("%d %d %d\n", m, a, b);
    return 0;
}