Cod sursa(job #2484313)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 30 octombrie 2019 22:24:10
Problema Xor Max Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 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=20; 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=20; 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;
    add(0);
    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(poz >= i) continue;
        if(ma<val){
            ma = val;
            a = poz;
            b = i;
        }
        else if(ma==val){
            if(i<b){
                b = i;
                a = poz;
            }
            else if(i == b)
                a = max(a,poz);
        }
    }
    out << ma << ' ' << a+1 << ' ' << b;
}