Cod sursa(job #2750397)

Utilizator NashikAndrei Feodorov Nashik Data 11 mai 2021 00:16:01
Problema Xor Max Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int v[100005],curr,d[2200005][3];
void add(int a){
    string s="",ss="";
    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=s.size();
    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){
    string s="",ss="";
    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=s.size(),rasp=0;
    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()
{
    int n;
    cin>>n;
    add(0);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        v[i]=(v[i] ^ v[i-1]);
        //cout<<v[i]<<" ";
        add(v[i]);
    }
    //cout<<"\n\n\n";
    int maxim=v[n],k=n;
    for(int i=1;i<=n;i++){
        int x=compare(v[i]);
        //cout<<v[i]<<" "<<x<<"\n";
        if(maxim<x){
            maxim=x;
            k=i;
        }
        maxim=max(maxim,x);
    }
    //cout<<"\n\n\n";
    cout<<maxim<<" ";
    if(maxim==v[k]){
        cout<<1<<" "<<k;
        return 0;
    }
    for(int i=1;i<=n;i++){
        if((v[i] ^ v[k])==maxim){
            int x1=i;
            int x2=k;
            if(x1>x2)
                swap(x1,x2);
            cout<<x1+1<<" "<<x2;
            return 0;
        }
    }
    return 0;
}