Cod sursa(job #2159560)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 11 martie 2018 00:30:19
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

struct trie{
    trie *f[2];
    trie(){
        memset(f, 0, sizeof(f));
    }
};

int n, pr[100005], mx=-1, st, dr;
trie *rad = new trie;
unordered_map<int, int> m;

int main()
{
    ifstream fin ("xormax.in");
    ofstream fout ("xormax.out");
    fin >> n;
    trie *t = rad;
    for (int i = 0; i < 20; ++i){
        t->f[0] = new trie;
        t = t->f[0];
    }
    m[0] = 0;
    for (int i = 1; i <= n; ++i){
        int x;
        fin >> x;
        pr[i] = pr[i-1]^x;
        m[pr[i]] = i;
        x = pr[i];
        int pw = (1<<20);
        t = rad;
        while(pw){
            int bit = 0;
            if(x >= pw)
                x -= pw, ++bit;
            if(t->f[bit] == NULL)
                t->f[bit] = new trie;
            t = t->f[bit];
            pw /= 2;
        }
        int sol = 0;
        x = pr[i];
        pw = (1<<20);
        t = rad;
        while(pw){
            int bit = 0;
            if(x >= pw)
                x -= pw, ++bit;
            if(t->f[1-bit] != NULL){
                if(1-bit == 1)
                    sol += pw;
                t = t->f[1-bit];
            }else{
                if(bit == 1)
                    sol += pw;
                t = t->f[bit];
            }
            pw /= 2;
        }
        if((sol^pr[i]) > mx){
            mx = sol^pr[i];
            st = m[sol]+1;
            dr = i;
        }
        mx = max(mx, sol^pr[i]);
    }
    fout << mx << " " << st << " " << dr << "\n";
    return 0;
}