Cod sursa(job #2594408)

Utilizator bigmixerVictor Purice bigmixer Data 5 aprilie 2020 22:23:09
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mod=1e9+7;
const int modp=1999999973;
const int modulo=998244353;

const int nmax=100005;

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

struct Trie{
    int val,app[2],num,index;
}tz;

vector<Trie>vecc;

int getres(int x){
    int indx=0;
    for(int i=20;i>=0;i--){
        int c = ((x&(1<<i))>0 ? 0:1);
        if(vecc[indx].app[c] && vecc[vecc[indx].app[c]].val>=1){}
        else c = (c==0? 1:0);
        indx=vecc[indx].app[c];
    }
    int g=(x^vecc[indx].num);
    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=((x&(1<<i))>0 ? 1:0);
        aux.push_back(indx);
        if(vecc[indx].app[c]==0){
            vecc[indx].app[c]=vecc.size();
            vecc.push_back(tz);
            indx=vecc.size()-1;
        }
        else indx=vecc[indx].app[c];
        if(i==0){
            vecc[indx].num=x;
            vecc[indx].val++;
            vecc[indx].index=y;
        }
    }
    aux.push_back(indx);
    for(int i=aux.size()-2;i>=0;i--) vecc[aux[i]].val+=vecc[aux[i+1]].val;
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
   // ifstream cin("xormax.in");
   // ofstream cout("xormax.out");
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    vecc.push_back(tz);
    buildtrie(0,0);
    for(int i=1;i<=n;i++){
        curr=(curr^a[i]);
        int g=getres(curr);
        if(ans<g){
            ans=g;
            last=i;
            first=tazik+1;
        }
        buildtrie(curr,i);
    }
    if(ans==0) cout << 0 << ' ' << n << ' ' << n;
    else cout << ans << ' ' << first << ' ' << last;
}