Cod sursa(job #3149673)

Utilizator divadddDavid Curca divaddd Data 10 septembrie 2023 21:05:57
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
const int LMAX = 31;
const int NMAX = 1e5+2;
int n,x,pref[NMAX];

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct BitTrie{
    int idx = 0;
    BitTrie * children[2] = {nullptr};
} root;

void add(int x, int id){
    BitTrie * ptr = &root;
    for(int i = LMAX; i >= 0; i--){
        int bit = (x>>i)&1;
        if(ptr->children[bit] == nullptr){
            BitTrie * new_branch = new BitTrie;
            ptr->children[bit] = new_branch;
            ptr = new_branch;
        }else{
            ptr = ptr->children[bit];
        }
    }
    ptr->idx = id;
}

int get_best_approx(int x){
    BitTrie * ptr = &root;
    for(int i = LMAX; i >= 0;  i--){
        int bit = (x>>i)&1;
        if(ptr->children[bit] != nullptr){
            ptr = ptr->children[bit];
        }else{
            ptr = ptr->children[!bit];
        }
    }
    return ptr->idx;
}

int main()
{
    fin >> n;
    int maxi = -1, l = 0, r = 0;
    add(0, 0);
    for(int i = 1; i <= n; i++){
        fin >> x;
        pref[i] = pref[i-1]^x;

        int ind = get_best_approx(~pref[i]);
        int val = pref[i]^pref[ind];
        if(val > maxi){
            maxi = val;
            l = ind+1, r = i;
        }

        add(pref[i], i);
    }
    fout << maxi << " " << l << " " << r;
    return 0;
}