Cod sursa(job #3144732)

Utilizator SSKMFSS KMF SSKMF Data 10 august 2023 12:31:49
Problema Xor Max Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
using namespace std;

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

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

                case 1: 
                {
                    if (!urmatorul[1]) urmatorul[1] = new Trie;
                    urmatorul[1] -> insert(valoare , _indice , bit - 1);
                }
                break;
            }
        }
        pair <int , int> find (const int valoare , const int bit) {
            if (bit == -1) return make_pair(0 , indice);
            if (valoare >> bit & 1)
            {
                pair <int , int> rezultat = (urmatorul[0] ? urmatorul[0] -> find(valoare , bit - 1) : urmatorul[1] -> find(valoare , bit - 1));
                if (urmatorul[0]) rezultat.first |= (1 << bit);
                return rezultat;
            }

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

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

    aparitii.insert(0 , 0 , 20);
    int valoare_maxima = 0 , inceput = 0 , sfarsit = 0;
    for (int indice = 1 , valoare , valoare_actuala = 0 ; indice <= lungime ; indice++)
    {
        cin >> valoare;

        valoare_actuala ^= valoare;
        pair <int , int> valoare_gasita = aparitii.find(valoare_actuala , 20);
        if (valoare_gasita.first > valoare_maxima || (valoare_gasita.first == valoare_maxima && indice - valoare_gasita.second < sfarsit - inceput + 1))
            { valoare_maxima = valoare_gasita.first; inceput = valoare_gasita.second + 1; sfarsit = indice; }

        aparitii.insert(valoare_actuala , indice , 20);
    }

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