Cod sursa(job #2484320)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 30 octombrie 2019 22:36:34
Problema Xor Max Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
struct nod{
    nod *n[2];
    vector<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.push_back(poz);
}
vector<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;
    int ma=-1,a=-1,b=-1;
    for(int i=1; i<=n; i++){
        in >> v[i];
        v[i]=v[i]^v[i-1];
        if(ma<v[i]){
            ma=v[i];
            a=0;
            b=i;
        }
        add(i);
    }
    for(int i=1; i<=n; i++){
        vector<int> pz = fnd_max(i);
        int val = v[pz[0]]^v[i];
        for(auto poz:pz){
            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;
}