Cod sursa(job #2484308)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 30 octombrie 2019 22:12:23
Problema Xor Max Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 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;
    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++){
        vector<int> pz = fnd_max(i);
        for(auto poz:pz){
            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;
}