Cod sursa(job #2615773)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 15 mai 2020 14:49:01
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int NMAX = 100005;
const int INF = (1<<29);
int a[NMAX],rasp,n,maxim,aux,st,dr;

struct Trie{
    int poz;
    Trie *fiu[2];
    Trie(){
        poz=0;
        fiu[0]=fiu[1]=NULL;
    }
};

Trie *root = new Trie;

void Insert(Trie *nod,int bit,int poz,int val){
    if(bit==-1){
        nod->poz = poz;
        return;
    }
    if(((val>>bit)&1)==0){
        if(nod->fiu[0]==NULL) nod->fiu[0] = new Trie;
        Insert(nod->fiu[0],bit-1,poz,val);
    } else {
        if(nod->fiu[1]==NULL) nod->fiu[1] = new Trie;
        Insert(nod->fiu[1],bit-1,poz,val);
    }
}

void Cauta(Trie *nod,int bit,int val){
    if(bit==-1){
        rasp = nod->poz;
        return;
    }
    int nr = ((val>>bit)&1);
    if(nod->fiu[1-nr]==NULL) Cauta(nod->fiu[nr],bit-1,val);
    else                     Cauta(nod->fiu[1-nr],bit-1,val);
}

int main()
{
    fin >> n;
    maxim = -INF;
    for(int i=1;i<=n;i++){
        fin >> a[i];
        if(a[i]>maxim) maxim=a[i];
        a[i]=a[i]^a[i-1];
    }
    int b=0;
    while(maxim!=0){
        maxim/=2;
        b++;
    }
    Insert(root,b,0,0);
    maxim = -INF;
    for(int i=1;i<=n;i++){
        Cauta(root,b,a[i]);
        if((a[i]^a[rasp])>maxim){
            maxim=(a[i]^a[rasp]);
            dr=i;
            st=rasp+1;
        }
        Insert(root,b,i,a[i]);
    }
    fout << maxim << ' ' << st << ' ' << dr;
    return 0;
}