Cod sursa(job #3189898)

Utilizator PetraPetra Hedesiu Petra Data 6 ianuarie 2024 17:17:27
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>

#define x first
#define poz second

using namespace std;

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


struct trie {
    int val, poz;
    trie *bit[2];
    trie() {
        val = poz = 0;
        bit[0] = bit[1] = NULL;
    }
};

trie *T = new trie;

void ins(trie *nod, int x, int poz)
{
    for (int i = 20; i >= 0; i--)
    {
        int bit = (x >> i) & 1;

        if (nod->bit[bit] == 0)
            nod->bit[bit] = new trie;

        nod = nod->bit[bit];
    }
    nod->val = x;
    nod->poz = poz;

    /* if (bit == 20)
    {
        nod->k++;
        return;
    }
    if (nod->bit[x%2] == 0)
        nod->bit[x%2] = new trie;

    ins(nod->bit[x%2], x/2, bit+1);
    nod->k++; */
}

pair<int, int> trie_query(trie *nod, int x)
{
    for (int i = 20; i >= 0; i--)
    {
        int bit = (x >> i) & 1;

        if(nod->bit[!bit] != 0)
            nod = nod->bit[!bit];
        else
            nod = nod->bit[bit];
    }
    return make_pair(nod->val, nod->poz);
}

int n, mx = -1, st, dr;
int main()
{
    fin >> n;

    int prefix = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        fin >> x;
        prefix ^= x;

        ins(T, prefix, i);

        pair<int, int> aux = trie_query(T, prefix);
        if (prefix ^ aux.x > mx)
        {
            mx = prefix ^ aux.x;
            st = aux.poz + 1;
            dr = i;
        }

    }
    fout << mx << " " << st << " " << dr;
    return 0;
}