Cod sursa(job #1593943)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 9 februarie 2016 00:21:14
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <cstring>
using namespace std;

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

int n,k,i,j,a,b,c,bit,y,poz,rasp,st,dr,p,x,r;
int v[100005];
struct Trie
{
    Trie* exista[2];
    int pozitie;
    Trie()
    {
        memset(exista, 0 , sizeof(exista));
        pozitie=0;
    }
};
int find(int bit, Trie* t)
{
    bool xx;
    if(a&bit)
        xx = 1;
    else
        xx = 0;
    if(bit == 0)
        return t->pozitie;
    if(t->exista[!xx] != 0)
    {
        if(bit > 1)
            return find(bit/2, t->exista[!xx]);
        else
            return find(0, t->exista[!xx]);
    }
    else
    {
        if(bit > 1)
            return find(bit/2, t->exista[xx]);
        else
            return find(0, t->exista[xx]);
    }
}
void add(int bit, Trie* t)
{
    bool xx;
    if(a&bit)
        xx = 1;
    else
        xx = 0;
    if(bit == 0)
    {
        t->pozitie = i;
        return ;
    }
    if(t->exista[xx] == 0)
        t->exista[xx] = new Trie;
    if(bit > 1)
        add(bit/2, t->exista[xx]);
    else
        add(0, t->exista[xx]);

}
int main()
{
    fin >> n;
    Trie *t = new Trie;
    bit = 1 << 20;
    add(bit, t);
    for(i = 1; i <= n; i++)
    {
       fin >> v[i];
       v[i] ^= v[i - 1];
       a = v[i];
       poz = find(bit,t);
       if((a ^ v[poz]) > rasp)
       {
           rasp = a ^ v[poz];
           st = poz + 1;
           dr = i;
       }
       add(bit, t);
    }
    fout << rasp << " " << st << " " << dr;
}