Cod sursa(job #2297678)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 6 decembrie 2018 10:50:40
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, prefix, ans, start, stop;

struct Trie{

    int value, poz;
    Trie *next[2];
    Trie(){
        value = poz = 0;
        next[0] = next[1] = NULL;

    }

};

Trie *T = new Trie;

void Insert(Trie *L, int i)
{
    Trie *nod = L;
    for(int i = 25; i >= 0; i--)
    {
        bool val = (prefix&(1<<i));

        if(nod->next[val] == NULL)
            nod->next[val] = new Trie;
        nod = nod->next[val];


    }
    nod->value = prefix;
    nod->poz = i;

}

void Xor(Trie *nod, int st)
{

    for(int i = 25; i >= 0; i--)
    {
        bool val = (prefix&(1<<i));
        if(nod->next[1-val])
            nod = nod->next[1-val];
        else
            if(nod->next[val])
                nod = nod->next[val];

    }

    int subarray = ((nod->value)^prefix);
    if(subarray >= prefix)
    {
        if(subarray > ans)
        {
            ans = subarray;
            start = nod->poz+1;
            stop = st;
        }
    }
    else
        if(prefix > ans)
        {
            ans = prefix;
            start = 1;
            stop = st;
        }
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
       int x;
       fin >> x;
       prefix  = prefix^x;
       Insert(T, i);
       Xor(T, i);
    }
    fout << ans << " " << start << " " << stop;

    return 0;
}