Cod sursa(job #2615862)

Utilizator AokijiAlex M Aokiji Data 15 mai 2020 18:36:57
Problema Xor Max Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

struct Trie
{
    int nr, lst;
    Trie *fiu[2];
    Trie () {
        nr = lst = 0;
        fiu[0] = fiu[1] = 0;
    }
};

int now;

Trie *T = new Trie;

void upd (Trie *nod, int nr, int p)
{
    nod->lst = now;
    if (p == 0)
    {
        return;
    }
    if (nod->fiu[nr / p % 2] == 0)
    {
        nod->fiu[nr / p % 2] = new Trie;
    }
    upd (nod->fiu[nr / p % 2], nr, p / 2);
}


pair <int, int> go (Trie *nod, int nr, int p, int val)
{
    if (p == 0)
    {
        return {val, nod->lst};
    }
    if (nod->fiu[1 - nr / p % 2] != 0)
        return go (nod->fiu[1 - nr / p % 2], nr, p / 2, val + p);
    else
        return go (nod->fiu[nr / p % 2], nr, p / 2, val);
}

int main()
{
    freopen ("xormax.in", "r", stdin);
    freopen ("xormax.out", "w", stdout);
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    int xr = 0;
    int x;
    int ans = 0, ansl = 0, ansr = 0;
    now = 0;
    upd (T, 0, 1 << 21);
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        now = i;
        xr ^= x;
        auto best = go (T, xr, 1 << 21, 0);
        if (best.first > ans)
        {
            ans = best.first;
            ansl = best.second + 1;
            ansr = i;
        }
        upd (T, xr, 1 << 21);
    }
    cout << ans << " " << ansl << " " << ansr << "\n";
    return 0;
}