Cod sursa(job #2055024)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 2 noiembrie 2017 19:07:17
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int Nmax=  100000 + 5;
int s[Nmax], x, xormax = -1;
struct trie
{
    trie *fiu[2];
    int terminal;
    trie()
    {
        fiu[0] = 0;fiu[1] = 0;
        terminal = 0;
    }
};
trie *T = new trie;
void adauga(trie *nod, int put, int nr, int prov)
{
    bool bit = (1 << put) & nr;
    if(put == -1)
    {
        nod->terminal = prov;
        return;
    }
    if(nod ->fiu[bit] == 0)nod -> fiu[bit] = new trie;
    adauga(nod->fiu[bit], put - 1, nr, prov);
}
int cauta(trie *nod, int put, int nr)
{
    if(put == -1)return nod->terminal;
    bool bit = nr & (1 << put);
    if(nod->fiu[!bit] == 0)
        return cauta(nod->fiu[bit], put - 1, nr);
    return cauta(nod->fiu[!bit], put -1, nr);
}
int main()
{
    adauga(t, 21,0, 0);
    for(int i = 1; i <= n; ++i)
    {
        fin >> a;
        s[i] = s[i - 1] ^ a;
        int poz = cautare(t, 21, s);
        x = s[i] ^ s[poz];
        if(xormax < x)
        {
            xormax = x;
            beg = poz + 1;
            finl = i;
        }
    }
    fout << xormax << " " << beg << " " << finl;
    return 0;
}