Cod sursa(job #3152780)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 26 septembrie 2023 19:00:44
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

struct trie
{
    int nr;
    trie *fii[2];
};
trie *initial = new trie();

const int NMAX = 1e5 + 5;
int n, v[NMAX], valxor;
unordered_map<int, int> poz;

void adauga(trie *t, int val, int bit)
{
    if(bit == -1)
        return;
    bool curr_bit = val & (1 << bit);
    t -> nr++;

    if(t -> fii[curr_bit] == NULL)
        t -> fii[curr_bit] = new trie();

    adauga(t -> fii[curr_bit], val, bit - 1);
}

void get_max(trie *t, int val, int bit)
{
    if(bit == -1)
        return;
    bool curr_bit = val & (1 << bit);
    if(t -> fii[!curr_bit] != NULL && t -> fii[!curr_bit] -> nr)
    {
        valxor += 1 << bit;
        get_max(t -> fii[!curr_bit], val, bit - 1);
        return;
    }
    get_max(t -> fii[curr_bit], val, bit - 1);
}

void citire()
{
    cin >> n;
    cin >> v[1];
    for(int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        v[i] = v[i - 1] ^ x;
    }
}

void solve()
{
    int max1 = 0, maxst = -NMAX - 2, maxdr = 0;
    for(int i = 1; i <= n; i++)
    {
        valxor = 0;
        adauga(initial, v[i], 21);
        poz[v[i]] = i;
        get_max(initial, v[i], 21);
        if(max1 < valxor)
        {
            max1 = valxor;
            maxst = poz[valxor & v[i]] - 1;
            maxdr = i;
        }
        else if(max1 == valxor && i - poz[valxor & v[i]] + 1 < maxdr - maxst)
        {
            maxst = poz[valxor & v[i]] - 1;
            maxdr = i;
        }
    }
    cout << max1 << " " << maxst << " " << maxdr;
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    citire();
    solve();
}