Cod sursa(job #2594476)

Utilizator bigmixerVictor Purice bigmixer Data 6 aprilie 2020 01:23:59
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

const int nmax=100005;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n,a[nmax],curr,ans,last=1,first=1,tazik;

struct Trie{
    int val,app[2],index;
    Trie(){
        app[0] = app[1] = index = 0;
    }
};

vector<Trie>vecc;

int getres(int x){
    int indx=0;
    int lmaooo=0;
    for(int i=20;i>=0;i--){
        int c = 0;
        if(x&(1<<i)) c=0;
        else c=1;
        if(vecc[indx].app[c]){}
        else c = (c^1);
        lmaooo+=c*(1<<i);
        indx=vecc[indx].app[c];
    }
    int g=(x^lmaooo);
    tazik=vecc[indx].index;
    return g;
}

void buildtrie(int x,int y){
    int indx=0;
    vector<int>aux;
    for(int i=20;i>=0;i--){
        int c=0;
        if(x&(1<<i)) c=1;
        else c=0;
        aux.push_back(indx);
        if(vecc[indx].app[c]==0){
            vecc[indx].app[c]=vecc.size();
            vecc.emplace_back();
        }
        indx=vecc[indx].app[c];
    }
    vecc[indx].index=y;
}

int main(){
    fin >> n;
    vecc.push_back(tz);
    buildtrie(0,0);
    for(int i=1;i<=n;i++){
        fin >> a[i];
        curr=(curr^a[i]);
        int g=getres(curr);
        if(ans<g){
            ans=g;
            last=i;
            first=tazik+1;
        }
        buildtrie(curr,i);
    }
    fout << ans << ' ' << first << ' ' << last;
}