Cod sursa(job #1593932)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 8 februarie 2016 23:54:46
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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[2];
    Trie()
    {
        exista[1]=exista[0]=0;
        pozitie[1]=pozitie[0]=0;
    }
};
int find(int bit, Trie* t)
{
    if(t->exista[!(a&bit)] != 0)
    {
        if(bit == 1)
            return t->pozitie[!(a&bit)];
        return find(bit/2, t->exista[!(a&bit)]);
    }
    else
    {
        if(bit == 1)
            return t->pozitie[(a&bit)];
        return find(bit/2, t->exista[(a&bit)]);
    }
}
void add(int bit, Trie* t)
{
    if(t->exista[(a&bit)] == 0)
        t->exista[(a&bit)] = new Trie;
    if(bit > 1)
        add(bit/2, t->exista[(a&bit)]);
    else
        t->pozitie[(a&bit)] = i;
}
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;
}