Cod sursa(job #2531182)

Utilizator rapunzelMihnea Andreescu rapunzel Data 25 ianuarie 2020 20:30:14
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>

using namespace std;

ifstream cin("xormax.in");
ofstream cout("xormax.out");

const int N = (int) 1e5 + 7;
int n;
int pref[N];
int sol = 0;
int id1;
int id2;

struct trie
{
    trie *kid[2];
    trie()
    {
        kid[0] = kid[1] = 0;
    }
};

trie *root = new trie;

void ins(int x)
{
    trie *cur = root;
    for (int bit = 21; bit >= 0; bit--)
    {
        int go;
        if (x & (1 << bit))
        {
            go = 1;
        }
        else
        {
            go = 0;
        }
        if (!cur->kid[go])
        {
            cur->kid[go] = new trie;
        }
        cur = cur->kid[go];
    }
}

int get(int val)
{
    int sol = 0;
    trie *cur = root;
    for (int bit = 21; bit >= 0; bit--)
    {
        if (!cur->kid[0] && !cur->kid[1])
        {
            break;
        }
        int go;
        if (val & (1 << bit))
        {
            go = 0;
        }
        else
        {
            go = 1;
        }
        if (cur->kid[go])
        {
            sol += (1 << bit);
            cur = cur->kid[go];
        }
        else
        {
            cur = cur->kid[1 ^ go];
        }
    }
    return sol;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        pref[i] = pref[i - 1] ^ x;
        int now = get(pref[i]);
        if (now > sol)
        {
            sol = now;
            id2 = i;
        }
        ins(pref[i]);
    }
    id1 = id2;
    while (pref[id1 - 1] != (sol ^ pref[id2]))
    {
        id1--;
    }
    cout << sol << " " << id1 << " " << id2 << "\n";


}