Cod sursa(job #2531181)

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

using namespace std;

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

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 = 20; bit >= 0; bit--)
    {
        int cb;
        if (x & (1 << bit))
        {
            cb = 1;
        }
        else
        {
            cb = 0;
        }
        if (!(cur->kid[cb]))
        {
            cur->kid[cb] = new trie;
        }
        cur = cur->kid[cb];
    }
}

int fmax(int x)
{
    trie *cur = root;
    int sol = 0;
    for (int bit = 20; bit >= 0; bit--)
    {
        if (!(cur->kid[0]) && !(cur->kid[0]))
        {
            break;
        }
        int cb;
        if (x & (1 << bit))
        {
            cb = 0;
        }
        else
        {
            cb = 1;
        }
        if (cur->kid[cb])
        {
            sol += (1 << bit);
            cur = cur->kid[cb];
        }
        else
        {
            cur = cur->kid[1 ^ cb];
        }
    }
    return sol;
}

const int N = 100000 + 7;

int main()
{
    int n, sol = 0, x[N], one = 1, two;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i];
        x[i] ^= x[i - 1];
        int now = fmax(x[i]);
        if (now > sol)
        {
            sol = now;
            two = i;
        }
        ins(x[i]);
    }
    one = two;
    while (x[one - 1] != (x[two] ^ sol))
    {
        one--;
    }
    cout << sol << " " << one << " " << two << "\n";
}