Cod sursa(job #1593936)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 9 februarie 2016 00:14:36
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 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)
{
    bool x;
    if(a&bit)
        x = 1;
    else
        x = 0;
    if(t->exista[!(x)] != 0)
    {
        if(bit == 1)
            return t->pozitie[!(x)];
        find(bit/2, t->exista[!(x)]);
    }
    else
    {
        if(bit == 1)
            return t->pozitie[(x)];
        find(bit/2, t->exista[(x)]);
    }
}
void add(int bit, Trie* t)
{
    bool x;
    if(a&bit)
        x = 1;
    else
        x = 0;
    if(t->exista[x] == 0)
        t->exista[x] = new Trie;
    if(bit > 1)
        add(bit/2, t->exista[x]);
    else
        t->pozitie[x] = 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;
}