Cod sursa(job #3302110)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 3 iulie 2025 14:10:22
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int NMAX = 1e5 + 1, BITMAX = 21;
int n, a[NMAX], prefix_xor[NMAX];

struct Node
{
    int poz;
    Node *children[2];
    Node()
    {
        poz = -1;
        children[0] = children[1] = nullptr;
    }
};
Node *root = new Node();

void adauga(int val, int poz)
{
    Node *node = root;
    for(int i = BITMAX - 1; i >= 0; i--)
    {
        int bit = ((val >> i) & 1);
        if(node->children[bit] == nullptr)
            node->children[bit] = new Node();
        node = node->children[bit];
    }
    node->poz = poz;
}

pair<int, int> query(int val)
{
    int ans = 0;
    Node *node = root;
    for(int i = BITMAX - 1; i >= 0; i--)
    {
        int bit = ((val >> i) & 1);
        if(node->children[1 - bit] != nullptr)
        {
            ans |= (1 << i);
            node = node->children[1 - bit];
        }
        else
            node = node->children[bit];
    }
    return {ans, node->poz};
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> a[i];
        prefix_xor[i] = (prefix_xor[i - 1] ^ a[i]);
    }
    adauga(0, 0);
    int vmax = -1, start = 1, finish = 1;
    for(int j = 1; j <= n; j++)
    {
        auto [val, poz] = query(prefix_xor[j]);
        if(val > vmax)
        {
            vmax = val;
            start = poz + 1;
            finish = j;
        }
        else if(val == vmax)
        {
            if(j < finish)
            {
                start = poz + 1;
                finish = j;
            }
            else if(j == finish)
            {
                if((j - (poz + 1) + 1) < (finish - start + 1))
                {
                    start = poz + 1;
                    finish = j;
                }
            }
        }
        adauga(prefix_xor[j], j);
    }
    fout << vmax << " " << start << " " << finish;

    fin.close();
    fout.close();
    return 0;
}