Cod sursa(job #2750437)

Utilizator NashikAndrei Feodorov Nashik Data 11 mai 2021 09:37:55
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int v[100005],curr,d[2200005][3],prod[25];
void add(int a){
    int cop=a,cnt=0;
    /*
    while(cop){
        ss+=char('0'+cop%2);
        cnt++;
        cop/=2;
    }
    for(int i=1;i<=22-cnt;i++){
        s+='0';
    }
    for(int i=ss.size()-1;i>=0;i--){
        s+=ss[i];
    }
    //cout<<a<<" "<<s<<"\n";
    */
    int cur=0;
    int gigel=21;
    while(gigel!=-1){
        int y=(a/prod[gigel])%2;
        if(d[cur][y]==0){
            d[cur][y]=++curr;
        }
        cur=d[cur][y];
        gigel--;
    }
    /*
    for(int i=0;i<m;i++){
        if(d[cur][s[i]-'0']==0){
            d[cur][s[i]-'0']=++curr;
        }
        cur=d[cur][s[i]-'0'];
    }
    */
}
int compare(int a){
    int cop=a,cnt=0;
    /*
    while(cop){
        ss+=char('0'+cop%2);
        cnt++;
        cop/=2;
    }
    for(int i=1;i<=22-cnt;i++){
        s+='0';
    }
    for(int i=ss.size()-1;i>=0;i--){
        s+=ss[i];
    }
    */
    //cout<<a<<" "<<s<<"\n";
    int cur=0;
    int m,rasp=0;
    int gigel=21;
    while(gigel!=-1){
        int y=(a/prod[gigel])%2;
        y=1-y;
        rasp*=2;
        if(d[cur][y]==0){
            y=1-y;
        }
        rasp+=y;
        cur=d[cur][y];
        gigel--;
    }
    /*for(int i=0;i<m;i++){
        int y=s[i]-'0';
        y=1-y;
        rasp*=2;
        if(d[cur][y]==0){
            y=1-y;
        }
        rasp+=y;
        cur=d[cur][y];
    }
    */
    //cout<<rasp<<" "<<a<<"\n";
    return (rasp ^ a);
}
int main()
{
    prod[0]=1;
    for(int i=1;i<=22;i++){
        prod[i]=prod[i-1]*2;
    }
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    add(0);
    int maxim=-1,k=1;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        v[i]=(v[i] ^ v[i-1]);
        //cout<<v[i]<<" ";
        add(v[i]);
        int x=compare(v[i]);
        if(maxim<x){
            maxim=x;
            k=i;
        }
    }
    //cout<<"\n\n\n";
    //cout<<"\n\n\n";
    cout<<maxim<<" ";
    int sol=0;
    for(int i=1;i<k;i++){
        if((v[i] ^ v[k])==maxim){
            sol=i;
        }
    }

    cout<<sol+1<<" "<<k;
    return 0;
}