Cod sursa(job #220682)

Utilizator Mishu91Andrei Misarca Mishu91 Data 11 noiembrie 2008 23:48:56
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <cstring>

#define MAX_N 100005
#define MAX_B 20

int H[4 << MAX_B];
int N, Sol;

void update(int x, int ind)
{
    int q = 0;

    for(int i = MAX_B; i >= 0; --i)
    {
        if(x & (1 << i))
            q = (q + 1) << 1;
        else
            q = (q << 1) | 1;
        H[q] = ind;
    }
}

void solve()
{
    memset(H, -1,  sizeof H);
    update(0,0);

    scanf("%d", &N);

    int x, y, q, st = 1, en = 1, s = 0;
    for(int i = 1; i <= N; ++i)
    {
        y = 0, q = 0;

        scanf("%d",&x);
        s ^= x;

        for(int j = MAX_B; j >= 0; --j)
        {
            int v[2], c = (s & (1 << j)) != 0;
            v[0] = (q << 1) | 1, v[1] = (q + 1) << 1;

            if(H[v[!c]] != -1)
                c = !c;
            q = v[c];
            if(c)
                y |= 1 << j;
        }

        if(s ^ y > Sol)
            Sol = s ^ y, st = H[q] + 1, en = i;

        update(s, i);
    }

    printf("%d %d %d\n",Sol, st, en);
}

int main()
{
    freopen("xormax.in","rt",stdin);
    freopen("xormax.out","wt",stdout);

    solve();
}