Cod sursa(job #3189409)

Utilizator not_anduAndu Scheusan not_andu Data 5 ianuarie 2024 11:34:16
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "xormax.in"
#define OUTFILE "xormax.out"

const int BIT_MAX = 20;
const int N_MAX = 1e5 + 5;

struct Trie {

    int ind;
    Trie *children[2];

    Trie() : ind(0){
        children[0] = children[1] = nullptr;
    }

};

void insert(Trie* &node, int x, int poz, int ind){

    bool aux;
    (x & (1 << poz)) ? aux = 1 : aux = 0;

    if(node -> children[aux] == nullptr){
        node -> children[aux] = new Trie();
    }

    if(poz == 0){
        node -> children[aux] -> ind = ind;
        return;
    }

    insert(node -> children[aux], x, poz - 1, ind);

}

pair<int, int> query(Trie* node, int x, int poz, int mask){

    bool aux;
    (x & (1 << poz)) ? aux = 1 : aux = 0;

    if(poz == -1){
        return make_pair(mask, node -> ind);
    }
    else if(node -> children[!aux] != nullptr){
        return query(node -> children[!aux], x, poz - 1, (mask | (1 << poz)));
    }
    return query(node -> children[aux], x, poz - 1, (mask | (1 << poz)) ^ (1 << poz));

}

int n, best = -1, lft = -1, rgt = -1;
int v[N_MAX], sp[N_MAX];
Trie* root;

void solve(){

    cin >> n;

    root = new Trie();
    insert(root, 0, 20, 0);
    
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        sp[i] = sp[i - 1] ^ v[i];
        pair<int, int> ans = query(root, sp[i], 20, 0);
        if(best < ans.first){
            best = ans.first;
            lft = ans.second + 1;
            rgt = i;
        }
        insert(root, sp[i], 20, i);
    }

    cout << best << " " << lft << " " << rgt << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}