Pagini recente » Cod sursa (job #71491) | Cod sursa (job #957751) | Cod sursa (job #71828) | Monitorul de evaluare | Cod sursa (job #3355693)
#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;
}