Cod sursa(job #2594454)

Utilizator bigmixerVictor Purice bigmixer Data 6 aprilie 2020 00:58:21
Problema Xor Max Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 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=1,first=1,tazik;

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

vector<Trie>vecc;

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

int main(){
    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);
    }
    cout << ans << ' ' << first << ' ' << last;
}