Cod sursa(job #1510692)

Utilizator tudormaximTudor Maxim tudormaxim Data 25 octombrie 2015 15:18:37
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <cstdio>
using namespace std;
bool Trie[1 << 22];
int Map[1 << 21];
 
void add(int val)
{
    int node=1, i;
    for(i=20; i>=0; i--)
    {
        bool bit=(val>>i)&1;
        Trie[node<<1 | bit]=1;
        node=node<<1 | bit;
    }
}
 
int xormax(int val)
{
    int node=1, rez=0, i;
    for(i=20; i>=0; i--)
    {
        bool bit=(val>>i)&1;
        if(Trie[node<<1 | (bit^1)])
        {
            node=node<<1 | (bit^1);
            rez=rez+(1<<i);
        }
        else node=node<<1 | bit;
    }
    return rez;
}
 
int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    int n, sum=0, val, maxxor=-1, inc=-1, sf=-1, i, x;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        Map[sum]=i;
        add(sum);
        scanf("%d", &val);
        sum=sum^val;
        x=xormax(sum);
        if(x>maxxor)
        {
            maxxor=x;
            sf=i;
            inc=Map[sum^maxxor];
        }
    }
    printf("%d %d %d", maxxor, inc, sf);
    return 0;
}