Cod sursa(job #3353689)

Utilizator Razvan23Razvan Mosanu Razvan23 Data 9 mai 2026 19:53:40
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;

struct Nod
{
    Nod *leg[2];
    int idx;
    Nod()
    {
        leg[0] = leg[1] = NULL;
        idx = 0;
    }
};

class Trie
{
public:
    Nod *rad;
    Trie()
    {
        rad = new Nod();
    }
    void Add(int val, int poz)
    {
        Nod *p = rad;
        for (int i = 21; i >= 0; i--)
        {
            int bit = (val >> i) & 1;
            if (p->leg[bit] == NULL) p->leg[bit] = new Nod();
            p = p->leg[bit];
        }
        p->idx = poz;
    }
    pair<int, int> QueryMaxXor(int val)
    {
        Nod *p = rad;
        int max_xor = 0;
        for (int i = 21; i >= 0; i--)
        {
            int bit = (val >> i) & 1;
            int bit_opus = 1 - bit;
            if (p->leg[bit_opus] != NULL)
            {
                max_xor |= (1 << i);
                p = p->leg[bit_opus];
            }
            else if (p->leg[bit] != NULL) p = p->leg[bit];
            else break;
        }
        return {max_xor, p->idx};
    }
};

int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    int n;
    cin >> n;
    Trie A;
    A.Add(0, 0);
    int prefix_xor = 0;
    int maxim = -1;
    int start = -1;
    int stop = -1;
    for (int i = 1; i <= n; i++)
    {
        int x;
        fin >> x;
        prefix_xor ^= x;
        pair<int, int> rez = A.QueryMaxXor(prefix_xor);
        int p = rez.first;
        int st = rez.second + 1;
        if (p > maxim)
        {
            maxim = p;
            start = st;
            stop = i;
        }
        A.Add(prefix_xor, i);
    }
    fout << maxim << " " << start << " " << stop << "\n";
    fin.close();
    fout.close();
    return 0;
}