Cod sursa(job #2634937)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 12 iulie 2020 19:01:52
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;

struct Trie{
    int nr,last;
    Trie *fiu[2];
    Trie(){
        nr=last=0;
        fiu[0]=fiu[1]=0;
    }
};

int now;
Trie *T=new Trie;

void update(Trie *nod, int nr, int bit) {
    nod->last=now;
    if(bit<0)
        return;
    bool b=(1<<bit) & nr;
    if(nod->fiu[b]==NULL)
        nod->fiu[b]=new Trie;
    update(nod->fiu[b], nr, bit-1);
}

pair <int, int> best;

void solve(Trie *nod, int nr, int bit, int val) {
    if(bit<0){
        best=make_pair(val, nod->last);
        return;
    }
    bool b=(1<<bit) & nr;
    if(nod->fiu[1-b]!=NULL)
        solve(nod->fiu[1-b], nr, bit-1, val+(1<<bit));
    else
        solve(nod->fiu[b], nr, bit-1, val);
}

int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,xr=0,ans=-1,ansl=0,ansr=0;
    scanf("%d", &n);
    now=0;
    update(T, 0, 21);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d", &x);
        now=i;
        xr^=x;
        solve(T, xr, 21, 0);
        if(best.first>ans){
            ans=best.first;
            ansl=best.second+1;
            ansr=i;
        }
        update(T, xr, 21);
    }
    printf("%d %d %d", ans, ansl, ansr);
    return 0;
}