Cod sursa(job #2483589)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 29 octombrie 2019 22:14:11
Problema Xor Max Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
struct nod{
    nod *n[2];
    int poz;
};
int n,v[nmax];
nod *t = new nod;
void add(int poz){
    nod *p = t;
    for(int i=21; i>=0; i--){
        if(v[poz]&(1<<i)){
            if(!(p->n[1])){
                p->n[1] = new nod;
            }
            p = p->n[1];
        }
        else{
            if(!(p->n[0])){
                p->n[0] = new nod;
            }
            p = p->n[0];
        }
    }
    p->poz = poz;
}
int fnd_max(int poz){
    nod *p = t;
    for(int i=21; i>=0; i--){
        if(v[poz]&(1<<i)){
            if(!(p->n[0])){
                p = p->n[1];
            }
            else{
                p = p->n[0];
            }
        }
        else{
            if(!(p->n[1])){
                p = p->n[0];
            }
            else{
                p = p->n[1];
            }
        }
    }
    return p->poz;
}
int main(){
    in >> n;
    for(int i=1; i<=n; i++){
        in >> v[i];
        v[i]=v[i]^v[i-1];
        add(i);
    }
    int ma=-1,a=-1,b=-1;
    for(int i=1; i<=n; i++){
        int poz = fnd_max(i);
        int val = v[poz]^v[i];
        if(ma<val){
            ma = val;
            a = min(poz,i);
            b = max(poz,i);
        }
        else if(ma==val){
            if(max(poz,i)<b){
                b = max(poz,i);
                a = min(poz,i);
            }
            else if(max(poz,i) == b)
                a = max(a,min(poz,i));
        }
    }
    out << ma << ' ' << a+1 << ' ' << b;
}