Cod sursa(job #3351734)

Utilizator Iustin_Mircea2010Iustin Mircea Iustin_Mircea2010 Data 21 aprilie 2026 10:29:08
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>

using namespace std;

struct trienode{
    int cnt, id;
    trienode* child[2];
    trienode(){
        cnt = id = 0;
        child[0] = child[1] = nullptr;
    }
}*root;

void baga(trienode* node, int b, int x, int ids){
    if(b == -1){
        node->id = ids;
        return;
    }
    int c = 0;
    if(x & (1 << b)){
        c = 1;
    }
    if(node->child[c] == nullptr)
        node->child[c] = new trienode();
    node->child[c]->cnt++;
    baga(node->child[c], b - 1, x, ids);
}

void scoate(trienode* node, int b, int x){
    if(b == -1) return;
    int c = 0;
    if(x & (1 << b)){
        c = 1;
    }
    node->child[c]->cnt--;
    scoate(node->child[c], b - 1, x);
}

pair<int, int> afla(trienode* node, int b, int x){
    if(b == -1){
        return {0, node->id};
    }
    int c = 0;
    if(x & (1 << b)) c = 1;
    if(node->child[1 - c] == nullptr || node->child[1 - c]->cnt == 0){
        return afla(node->child[c], b - 1, x);
    }
    pair<int, int> ans = afla(node->child[1 - c], b - 1, x);
    return {ans.first + (1 << b), ans.second};
}

int v[100005];

int main(){

    ifstream cin("xormax.in");
    ofstream cout("xormax.out");

    root = new trienode();
    int n, ans = -1, l, r;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        v[i] ^= v[i - 1];
    }
    baga(root, 30, 0, 0);
    for(int i = 1; i <= n; i++){
        pair<int, int> here = afla(root, 30, v[i]);
        if(here.first > ans){
            ans = here.first;
            r = i;
            l = here.second + 1;
        }
        baga(root, 30, v[i], i);
    }
    cout << ans << " " << l << " " << r << '\n';


    return 0;
}