Cod sursa(job #1889482)

Utilizator Emil64Emil Centiu Emil64 Data 22 februarie 2017 18:57:31
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<bits/stdc++.h>

using namespace std;

int n, x[100010],sol=-1,st,dr,lim=22;

class Trie{

    Trie *st,*dr;
    public:
        int poz;
        Trie()
        {
            poz = 0;
            st = __null;
            dr = __null;
        }
        void update(int x, int poz, int nivel){

            if(nivel == 0){
                this->poz = poz;
                return;
            }
            int bit = x&(1<<nivel);
            if(bit){
                if(!this->st)
                    this->st = new Trie();
                this->st->update(x, poz, nivel-1);
            }
            else{
                if(!this->dr)
                    this->dr = new Trie();
                this->dr->update(x, poz, nivel-1);
            }
        }
        int query(int x, int nivel){
            if(nivel == 0)
                return this->poz;
            int bit = x&(1<<nivel);
            if(bit){
                if(!this->dr)
                    return this->st->query(x, nivel-1);
                else return this->dr->query(x, nivel-1);
            }
            else{
                if(!this->st)
                    return this->dr->query(x, nivel-1);
                else return this->st->query(x, nivel-1);
            }
        }
};

int main()
{
    ifstream f("xormax.in");
    ofstream g("xormax.out");
    f>>n;
    Trie* t = new Trie();
    int nr, i, j;
    t->update(0, 0, 22);
    for(i=1;i<=n;i++){

        f >> nr;
        x[i]=(x[i-1]^nr);
        j = t->query(x[i], 22);
        if(sol<(x[j]^x[i])){
            sol=(x[j]^x[i]);
            st=j;
            dr=i;
        }
        t->update(x[i], i, 22);
    }
    g<<sol<<' '<<(st+1)<<' '<<dr<<"\n";
}