Cod sursa(job #3348634)

Utilizator eric.mesterEric Mestereaga eric.mester Data 23 martie 2026 11:19:58
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>
#define NMAX 100002

using namespace std;

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

struct Trie{

    const int BITS = 22;
    Trie *children[2] = {nullptr, nullptr};
    int sz = 0;
    int idx;

    void add_child(int x)
    {
        children[x] = new Trie;
    }

    void insert(int val, int i, int depth = 0)
    {
        sz++;
        if(BITS + 1 == depth){
            idx = i;
            return;
        }
        int bit = 1<<(BITS - depth);
        if(val & bit){
            if(children[1] == nullptr) add_child(1);
            (*children[1]).insert(val, i, depth+1);
        }else{
            if(children[0] == nullptr) add_child(0);
            (*children[0]).insert(val, i, depth+1);
        }
    }

    void max_xor(int val, int &i,int & ret, int depth = 0)
    {
        if(BITS + 1 == depth){
            i = idx;
            return;
        }
        int bit = 1<<(BITS - depth);
        if(val & bit){///bitu ii 1
            if(children[0] != nullptr){
                (*children[0]).max_xor(val, i, ret, depth + 1);
            }else{
                ret += bit;
                (*children[1]).max_xor(val, i,ret, depth + 1);
            }
        }else{///bitu ii 0
            if(children[1] != nullptr){
                ret += bit;
                (*children[1]).max_xor(val, i,ret, depth + 1);
            }else{
                (*children[0]).max_xor(val, i,ret, depth + 1);
            }
        }
        return;
    }

    pair<int,int> max_xor(int val)
    {
        int ret = 0;
        int idx = 0;
        max_xor(val, idx, ret);
        return {idx,ret};
    }
};

Trie trie;
int N;
int a[NMAX];
int prefix_xor[NMAX];///puteam si sa il fac o singura variabila
int max_xor;
int le, ri;

int main()
{
    fin >> N;
    for(int i=1;i<=N;i++){
        fin >> a[i];
        prefix_xor[i] = a[i] ^ prefix_xor[i-1];
    }
    for(int i=1;i<=N;i++){
        trie.insert(prefix_xor[i-1], i-1);
        auto [idx, val] = trie.max_xor(prefix_xor[i]);
        if(max_xor < (val ^ prefix_xor[i])){
            max_xor = val ^ prefix_xor[i];
            le = idx + 1;
            ri = i;
        }
    }
    fout << max_xor << " " << le << " " << ri;
}