Cod sursa(job #3248718)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 12 octombrie 2024 20:53:59
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
using namespace std;

ifstream cin("xormax.in");
ofstream cout("xormax.out");

int v[100001];
bool c[21];
int trie[4194305];

int main()
{
    int n,i,j,nod,rasp=-1,st,dr;
    cin>>n;
    for(i=2;i<(1<<22);i++) trie[i]=-1;
    for(i=1;i<22;i++) trie[i]=0;
    for(i=1;i<=n;i++){
        cin>>v[i];
        v[i]^=v[i-1];
        for(j=0;j<21;j++){
            c[j]=(bool)(v[i]&(1<<(20-j)));
        }
        nod=1;
        for(j=0;j<21;j++){
            if(trie[2*nod+(c[j]==0)]>0) nod=2*nod+(c[j]==0);
            else nod=2*nod+c[j];
        }
        j=trie[nod];
        if((v[i]^v[j])>rasp){
            rasp=v[i]^v[j];
            st=j+1;dr=i;
        }
        nod=1;
        for(j=0;j<21;j++){
            nod=nod*2+c[j];
            trie[nod]=i;
        }
    }
    cout<<rasp<<" "<<st<<" "<<dr;
    return 0;
}