Cod sursa(job #3353177)

Utilizator mitoceanuci@gmail.comMitoceanu Ciprian [email protected] Data 5 mai 2026 13:03:45
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_BITS = 20;
const int MAX_NODES = 2500005;

int trie[MAX_NODES][2];
int leaf_index[MAX_NODES];
int nodes_count = 0;

void insert(int value, int original_index)
{
    int node = 0;
    for(int i = MAX_BITS;i>=0;i--)
    {
        int bit = (value >> i) & 1;
        if(trie[node][bit]==0)
        {
            trie[node][bit] = ++nodes_count;
        }
        node = trie[node][bit];
    }
    leaf_index[node] = original_index;
}

int query(int value)
{
    int node = 0;
    for(int i = MAX_BITS;i>=0;i--)
    {
        int bit = (value>>i) & 1;
        int opposite_bit = 1 - bit;
        if(trie[node][opposite_bit] != 0)
        {
            node = trie[node][opposite_bit];
        }
        else
        {
            node = trie[node][bit];
        }
    }
    return leaf_index[node];
}

int P[100005];

int main()
{
    
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;

    int max_xor = -1;
    int best_start = 0, best_stop = 0;

    int curent_prefix_xor = 0;

    insert(0,0);
    P[0] = 0;

    for(int i{1};i<=n;i++)
    {
        int val;
        cin>>val;
       
        P[i] = P[i - 1] ^ val;

        int best_k = query(P[i]);

        int candidate_xor = P[i] ^ P[best_k];

        if(candidate_xor>max_xor)
        {
            max_xor = candidate_xor;
            best_start = best_k + 1;
            best_stop = i;
        }

        insert(P[i], i);
    }

    cout<<max_xor<< " "<<best_start<< ' '<<best_stop;

    return 0;
}

/*
Solution:
We put the partial sums XOR in binary form in a Trie.
We choose the best number by comparing the bits and choosing
the one with the inversed bits.

*/