Cod sursa(job #2484348)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 30 octombrie 2019 23:26:08
Problema Xor Max Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 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;
    nod(){
        poz.clear();
        memset(n,0,sizeof(n));
    }
};
int n,v[nmax];
nod *t = new nod;
void add(int pz){
    nod *p = t;
    for(int i=20; i>=0; i--){
        if(v[pz]&(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(pz);
}
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;
}
bool is(int value){
    nod *p = t;
    for(int i=20; i>=0; i--){
        if(value&(1<<i)){
            if(!(p->n[1])) return false;
            else p=p->n[1];
        }
        else{
            if(!(p->n[0])) return false;
            else p=p->n[0];
        }
    }
    return true;
}
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 st = 0,dr = pz.size()-1;
        if(pz[0]>=i) continue;
        while(st<dr){
            int mid = dr-(dr-st)/2;
            if(i>pz[mid]) st=mid;
            else dr = mid-1;
        }
        int poz = pz[st];
        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;
}