Cod sursa(job #3324912)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 24 noiembrie 2025 00:12:31
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>

using namespace std;

ifstream f("xormax.in");
ofstream g("xormax.out");

struct Trie
{
    int val, pos;
    Trie *next[2];
    Trie(): val(0), pos(0)
    {
        next[0] = next[1] = NULL;
    }
} *root, *crt, *sol;

int n, x, l, r, sum, maxSum;

void Insert(int val, int pos)
{
    crt = root;
    for (int bit = 21; bit >= 0; bit--)
    {
        bool id = ((val >> bit) & 1);
        if (crt->next[id] == NULL)
            crt->next[id] = new Trie;
        crt = crt->next[id];
    }
    crt->val = val;
    crt->pos = pos;
}

Trie* FindPrefix(int val)
{
    crt = root;
    for (int bit = 21; bit >= 0; bit--)
    {
        bool id = ((val >> bit) & 1);
        if (crt->next[id ^ 1] != NULL)
            crt = crt->next[id ^ 1];
        else
            crt = crt->next[id];
    }
    return crt;
}

int main()
{
    root = new Trie;
    l = r = 0;
    maxSum = -1;
    sum = 0;
    ///
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> x;
        Insert(sum, i - 1);
        sum ^= x;
        sol = FindPrefix(sum);
        if ((sol->val ^ sum) > maxSum)
        {
            maxSum = (sol->val ^ sum);
            l = sol->pos + 1;
            r = i;
        }
    }
    ///
    g << maxSum << ' ' << l << ' ' << r;
    f.close();
    g.close();
    return 0;
}