Cod sursa(job #3250439)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 20 octombrie 2024 21:03:34
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("xormax.in");
ofstream cout("xormax.out");
#define NR_BIT 21

int frv[2100000];
int xr[100001];
struct trie{
    int next[2]={-1,-1};
    int cnt;
};
vector<trie> t;

void update(int a){
    int poz=0,urm,i;
    for(i=NR_BIT-1;i>=0;i--){
        if(a&(1<<i)) urm=1;
        else urm=0;
        if(t[poz].next[urm]==-1){
            t[poz].next[urm]=t.size();
            t.emplace_back();
        }
        poz=t[poz].next[urm];
    }
    t[poz].cnt++;
}

int query(int a){
    int poz=0,rasp=0,i,urm;
    for(i=NR_BIT-1;i>=0;i--){
        if(a&(1<<i)) urm=0;
        else urm=1;
        if(t[poz].next[urm]==-1) urm^=1;
        rasp=rasp*2+urm;
        poz=t[poz].next[urm];
    }
    return rasp;
}

int main()
{
    int n,i,aux,a,max1=-1,st,dr;
    cin>>n;t.emplace_back();
    update(0);frv[0]=0;
    for(i=1;i<=n;i++){
        cin>>a;
        xr[i]=xr[i-1]^a;
        aux=query(xr[i]);
        if((aux^xr[i])>max1){
            max1=aux^xr[i];
            st=frv[aux]+1;
            dr=i;
        }
        update(xr[i]);
        frv[xr[i]]=i;
    }
    cout<<max1<<" "<<st<<" "<<dr;
    return 0;
}