Cod sursa(job #1510520)

Utilizator tudormaximTudor Maxim tudormaxim Data 25 octombrie 2015 10:50:17
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
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()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    int n, sum=0, val, maxxor=-1, inc=-1, sf=-1, i, x;
    fin >> n;
    for(i=1; i<=n; i++)
    {
        Map[sum]=i;
        add(sum);
        fin >> val;
        sum=sum^val;
        x=xormax(sum);
        if(x>maxxor)
        {
            maxxor=x;
            sf=i;
            inc=Map[sum^maxxor];
        }
    }
    fout << maxxor << " " << inc << " " << sf;
    fin.close();
    fout.close();
    return 0;
}