Cod sursa(job #3355693)

Utilizator darius_cimbruDarius Cimbru darius_cimbru Data 25 mai 2026 00:45:03
Problema Xor Max Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

// pun toate prefix xor-urile intr-un trie binar pe 21 biti (de la bit 20 jos pana la 0)
// pentru fiecare r fac DFS pe tot trie-ul ca sa vad fiecare valoare deja inserata
// compar p[r] xor val pentru fiecare leaf si tin maximul plus index-ul (maxIdx la fiecare nod ca sa rezolv tiebreak-ul de lungime)

struct Nod {
    Nod *zero, *unu;
    int maxIdx;
};

Nod *radacina;
int queryVal;
int bestX, bestIdx;

void dfsAll(Nod *nod, int depth, int curVal){
    if(depth==21){
        int x=queryVal^curVal;
        if(x>bestX){
            bestX=x;
            bestIdx=nod->maxIdx;
        }
        return;
    }
    if(nod->zero) dfsAll(nod->zero, depth+1, curVal);
    if(nod->unu) dfsAll(nod->unu, depth+1, curVal | (1<<(20-depth)));
}

int main(){
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    int n;
    fin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) fin>>a[i];

    vector<int> p(n+1, 0);
    for(int i=1;i<=n;i++) p[i]=p[i-1]^a[i];

    radacina = new Nod();
    radacina->zero=NULL; radacina->unu=NULL; radacina->maxIdx=-1;

    int gBestX=-1, gBestStart=1, gBestEnd=1;

    for(int r=0;r<=n;r++){
        if(r>0){
            queryVal=p[r];
            bestX=-1;
            bestIdx=-1;
            dfsAll(radacina, 0, 0);
            if(bestX>gBestX){
                gBestX=bestX;
                gBestStart=bestIdx+1;
                gBestEnd=r;
            }
        }

        Nod *cur=radacina;
        for(int b=20;b>=0;b--){
            int bit=(p[r]>>b)&1;
            Nod **nxt;
            if(bit==0) nxt=&cur->zero;
            else nxt=&cur->unu;
            if(*nxt==NULL){
                Nod *nou=new Nod();
                nou->zero=NULL; nou->unu=NULL; nou->maxIdx=-1;
                *nxt=nou;
            }
            cur=*nxt;
            if(r>cur->maxIdx) cur->maxIdx=r;
        }
    }

    fout<<gBestX<<" "<<gBestStart<<" "<<gBestEnd<<"\n";
    return 0;
}