Cod sursa(job #2431275)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 18 iunie 2019 19:24:48
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e5 + 7;

int v[DIM];

struct Trie
{
    Trie *bit[2];
    int pos;

    Trie()
    {
        bit[0] = nullptr;
        bit[1] = nullptr;

        pos = -1;
    }

    void add(int nr, int pos)
    {
        Trie *curr = this;

        for(int i = 20; i >= 0; i--)
        {
            int nxt = ((nr & (1 << i)) != 0);

            if(curr -> bit[nxt] == nullptr)
            {
                curr -> bit[nxt] = new Trie;
            }

            curr = curr -> bit[nxt];
        }

        curr -> pos = max(curr -> pos, pos);
    }

    int query(int nr)
    {
        int ans = 0;
        Trie *curr = this;

        for(int i = 20; i >= 0; i--)
        {
            int nxt = (((nr & (1 << i)) != 0) ^ 1);

            if(curr -> bit[nxt] == nullptr)
            {
                nxt ^= 1;
            }

            curr = curr -> bit[nxt];
        }

        return curr -> pos;
    }

};

Trie *trie = new Trie;

int main()
{
    int n;
    in >> n;

    for(int i = 1; i <= n; i++)
    {
        in >> v[i];

        v[i] ^= v[i - 1];
    }

    int best = v[1];
    int l = 1;
    int r = 1;

    trie -> add(v[1], 1);

    for(int i = 2; i <= n; i++)
    {
        int pos = trie -> query(v[i]);

        int val = v[i] ^ v[pos];

        if(val > best)
        {
            best = val;
            l = pos + 1;
            r = i;
        }

        trie -> add(v[i], i);
    }

    out << best << ' ' << l << ' ' << r;
}