Cod sursa(job #1449807)

Utilizator MaarcellKurt Godel Maarcell Data 10 iunie 2015 18:06:37
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
using namespace std;

struct Trie{
    Trie *l,*r;
    int val;
    Trie(){
        l=r=NULL;
        val=0;
    }
};

int N,a[100010],nr,ansl,ind; Trie *T=new Trie();

void ins(Trie *nod, int pb){
    if (pb<0){
        nod->val=ind;
        return;
    }

    if (nr&(1<<pb)){
        if (nod->r==NULL)
            nod->r=new Trie();
        ins(nod->r,pb-1);
        return;
    }

    if (nod->l==NULL) nod->l=new Trie();
    ins(nod->l,pb-1);
}

int fndmax(Trie *nod, int pb){
    if (pb<0){
        ansl=nod->val;
        return 0;
    }

    if (nr&(1<<pb)){
        if (nod->l) return fndmax(nod->l,pb-1);
        return (1<<pb)+fndmax(nod->r,pb-1);
    }

    if (nod->r) return (1<<pb)+fndmax(nod->r,pb-1);
    return fndmax(nod->l,pb-1);
}

int main(){
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    fin >> N;

    int i;
    for (i=1; i<=N; i++) fin >> a[i];

    nr=0;
    ind=0;
    ins(T,20);

    int MAX=0,cr=0,aux,lt,rt;
    for (i=1; i<=N; i++){
        cr^=a[i];
        nr=cr;

        aux=cr^fndmax(T,20);
        if (aux>MAX){
            MAX=aux;
            lt=ansl+1;
            rt=i;
        }
        ind=i;
        ins(T,20);
    }

    fout << MAX << " " << lt << " " << rt << "\n";
    return 0;
}