Cod sursa(job #2969821)

Utilizator AswVwsACamburu Luca AswVwsA Data 23 ianuarie 2023 19:08:41
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <map>
#include <algorithm>
#include <climits>
#define ll long long
using namespace std;

const int NMAX = 1e5;

struct trie
{
    int poz;
    trie *vecini[2];
    trie()
    {
        poz = -1;
        for (int i = 0; i <= 1; i++)
            vecini[i] = nullptr;
    }
};
int i;
void adauga(trie *nod, int val, int pwr)
{
    if (pwr > -1)
    {
        bool bit = bool(val & (1 << pwr));

        if (nod->vecini[bit] == nullptr)
        {
            nod->vecini[bit] = new trie;
        }
        adauga(nod->vecini[bit], val, pwr - 1);
    }
    else
    {
        nod->poz = i;
        return ;
    }
}

int v[NMAX + 1];

int cauta(trie *nod, int val, int pwr)
{
    if (pwr == -1)
    {
        return nod->poz;
    }
    bool bit = (val & (1 << pwr));
    if (nod->vecini[!bit] != nullptr)
    {
        return cauta(nod->vecini[!bit], val, pwr - 1);
    }
    return cauta(nod->vecini[bit], val, pwr - 1);
}
int main()
{
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    trie *root = new trie;
    int n;
    cin >> n;
    adauga(root, 0, 20);
    int ans = 0;
    int st, dr;
    for (i = 1; i <= n; i++)
    {
        cin >> v[i];
        v[i] ^= v[i - 1];
        int cine = cauta(root, v[i], 20);
        if (ans < (v[i] ^ v[cine]))
        {
            ans = (v[i] ^ v[cine]);
            st = cine + 1;
            dr = i;
        }
        adauga(root, v[i], 20);
    }
    cout << ans << " " << st << " " << dr;
}