Cod sursa(job #2457465)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 17 septembrie 2019 20:24:54
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
#define maxi 100009

using namespace std;

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

struct trie
{
    trie *next[2];
    int last;
    int val;
    trie()
    {
        this -> val = 0;
        this -> last = 0;
        this -> next[0] = NULL;
        this -> next[1] = NULL;
    }
};

trie *root = new trie();

namespace task
{
    void add(trie *nod, const int val, const int id, int bit)
    {
        if (bit == -1) // asta e "frunza"
        {
            nod -> last = id;
            nod -> val = val;
            return;
        }
        int x = (val & (1 << bit));
        if (x > 0)
            x = 1;
        if (nod -> next[x] == nullptr)
            nod -> next[x] = new trie();
        add (nod -> next[x], val, id, bit - 1);
    }

    trie *query(trie *nod, const int val, int bit)
    {
        if (bit == -1)
            return nod;
        int x = (val & (1 << bit));
        if (x > 0)
            x = 1;
        assert(nod -> next[0] != nullptr || nod -> next[1] != nullptr);
        assert ((!x) == 0 || (!x) == 1);
        if (nod -> next[!x] != nullptr)
            return query(nod -> next[!x], val, bit - 1);
        else
        {
            assert(nod -> next[x] != nullptr);
            return query(nod -> next[x], val, bit - 1);
        }
    }

}

int main()
{
    int n;
    f >> n;
    task::add(root, 0, 0, 25);
    int Xor = 0;
    int max = 0, start = 1, stop = 1;
    for (int i = 1; i <= n; ++ i)
    {
        int a;
        f >> a;
        Xor = Xor ^ a;
        auto Q = task::query(root, Xor, 25);
        assert(Q != nullptr);
        if ((Q -> val ^ Xor) > max)
        {
            max = Q -> val ^ Xor;
            start = Q -> last + 1;
            stop = i;

        }
        task::add(root, Xor, i, 25);
    }
    g << max << " " << start << " " << stop;;
}