Cod sursa(job #2452317)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 30 august 2019 14:19:39
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include<bits/stdc++.h>
using namespace std;
struct nod{
    int st , dr , poz;
};

nod v[2100100];

int cont = 1;

void nou (int nod , int tip){
    if (tip == 0){
        if (v[nod].st == 0){
            cont++;
            v[nod].st = cont;
        }
    }
    else{
        if (v[nod].dr == 0){
            cont++;
            v[nod].dr = cont;
        }
    }
}

void update (int nod , int lv , int val , int poz){
    //cout<<nod<<" "<<lv<<" "<<val<<" "<<poz<<'\n';
    if (lv == 0){
        v[nod].poz = poz;
        return;
    }
    if (val & (1 << (lv-1))){
        nou (nod , 0);
        update (v[nod].st , lv-1 , val , poz);
    }
    else{
        nou (nod , 1);
        update (v[nod].dr , lv-1 , val , poz);
    }
}

int last[100100];

int scot = 0;

void query (int nod , int lv , int val){
    if (lv == 0){
        //cout<<"qr : "<<nod<<" "<<lv<<" "<<val<<'\n';
        scot = v[nod].poz;
        return;
    }
    if (val & (1 << (lv-1))){
        if (v[nod].dr){
            query (v[nod].dr , lv-1 , val);
        }
        else{
            query (v[nod].st , lv-1 , val);
        }
    }
    else{
        if (v[nod].st){
            query (v[nod].st , lv-1 , val);
        }
        else{
            query (v[nod].dr , lv-1 , val);
        }
    }
}
int main() {
    ifstream cin ("xormax.in");ofstream cout ("xormax.out");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << setprecision(10) << fixed;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    srand(time(nullptr));

    int n;
    cin>>n;

    int MAX = 0;
    pair < int , int > go = {1 , 1};
    update (1 , 21 , 0 , 0);

    for (int i=1; i<=n; i++){
        int nr;
        cin>>nr;
        last[i] = last[i-1] ^ nr;
        update(1 , 21 , last[i] , i);
        query(1 , 21 , last[i]);
        int now = last[i] ^ last[scot];
        //cout<<now<<" "<<scot<<" "<<i<<'\n';
        if (now > MAX){
            MAX = now;
            go = {scot+1 , i};
        }
    }

    cout<<MAX<<" "<<go.first<<" "<<go.second<<'\n';

    return 0;

}