Cod sursa(job #3164199)

Utilizator SSKMFSS KMF SSKMF Data 2 noiembrie 2023 13:53:09
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <fstream>
using namespace std;

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

class Trie {
    private:
        int indice = 0;
        Trie *urmatorul[2] = { };
    public:
        void insert (const int valoare , const int _indice , const int bit = 20) 
        {
            if (bit == -1) 
                { indice = _indice; }
            else
            {
                if (valoare & (1 << bit))
                {
                    if (!urmatorul[1]) { urmatorul[1] = new Trie; }
                    urmatorul[1] -> insert(valoare , _indice , bit - 1);
                }
                else
                {
                    if (!urmatorul[0]) { urmatorul[0] = new Trie; }
                    urmatorul[0] -> insert(valoare , _indice , bit - 1);
                }
            }
        }
        pair <int , int> find (const int valoare , const int bit = 20)
        {
            if (bit == -1)
                { return {0 , indice}; }

            if (((valoare & (1 << bit)) && urmatorul[0]) || !urmatorul[1])
                { return urmatorul[0] -> find(valoare , bit - 1); }

            if ((!(valoare & (1 << bit)) && urmatorul[1]) || !urmatorul[0])
            {
                pair <int , int> rezultat = urmatorul[1] -> find(valoare , bit - 1);
                rezultat.first |= (1 << bit);
                return rezultat;
            }

            pair <int , int> optiune_1 = urmatorul[0] -> find(valoare , bit - 1);
            pair <int , int> optiune_2 = urmatorul[1] -> find(valoare , bit - 1);
            optiune_2.first |= (1 << bit);

            if ((valoare ^ optiune_1.first) > (valoare ^ optiune_2.first))
                { return optiune_1; }

            return optiune_2;
        }
} optiuni;

int main ()
{
    int lungime;
    cin >> lungime;

    optiuni.insert(0 , 0);
    int maxim = -1 , inceput = 1 , sfarsit = 0;
    for (int dreapta = 1 , suma = 0 , valoare ; dreapta <= lungime ; dreapta++)
    {
        cin >> valoare;

        suma ^= valoare;
        pair <int , int> stanga = optiuni.find(suma);
        if ((stanga.first ^ suma) > maxim)
            { maxim = (stanga.first ^ suma); inceput = stanga.second + 1; sfarsit = dreapta; }

        optiuni.insert(suma , dreapta);
    }

    cout << maxim << ' ' << inceput << ' ' << sfarsit;
    cout.close(); cin.close();
    return 0;
}