Cod sursa(job #3039836)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 28 martie 2023 21:59:23
Problema Xor Max Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <fstream>

using namespace std;

const int NMAX = 100000;

int xorPartial[1 + NMAX]; /// xorPartial[i] = a1 xor a2 xor a3 xor ... xor ai
/// Ca la sume partiale.

///xorPartial[i - 1] ^ xorPartial[j] (pp. ca i <= j) = xorul elemenetelor ai, ai+1, ... , aj

class Trie
{
private:

    static const int SIGMA = 2;
    int frecventa;
    Trie* fii[Trie::SIGMA];
    Trie* tata;
    int pozInTata;

public:

    Trie() : frecventa(0), tata(nullptr), pozInTata(-1)
    {
        for (int i = 0; i < Trie::SIGMA; i++)
            this->fii[i] = nullptr;
    }

    void adauga(const string& s, int indexXor, int index = 0)
    {
        if (index >= s.size())
        {
            this->frecventa = indexXor;
            return;
        }

        if (this->fii[s[index] - '0'] == nullptr)
        {
            this->fii[s[index] - '0'] = new Trie();
            this->fii[s[index] - '0']->tata = this;
            this->fii[s[index] - '0']->pozInTata = s[index] - '0';
        }

        this->fii[s[index] - '0']->adauga(s, indexXor, index + 1);
    }

    int solutie(const string& s, int& solIndex, int index = 0, int adancime = 20)
    {
        if (index >= s.size())
        {
            solIndex = this->frecventa;
            return 0;
        }

        if (s[index] == '1' && this->fii[0] != nullptr)
        {
            return (1 << adancime) + this->fii[0]->solutie(s, solIndex, index + 1, adancime - 1);
        }
        else if (s[index] == '1')
        {
            return this->fii[1]->solutie(s, solIndex, index + 1, adancime - 1);
        }
        else if (s[index] == '0' && this->fii[1] != nullptr)
        {
            return (1 << adancime) + this->fii[1]->solutie(s, solIndex, index + 1, adancime - 1);
        }
        else
        {
            return this->fii[0]->solutie(s, solIndex, index + 1, adancime - 1);
        }
    }

    ~Trie()
    {
        for (int i = 0; i < Trie::SIGMA; i++)
            if (this->fii[i] != nullptr)
                delete this->fii[i];
    }
};

string toString(int x)
{
    string sol = "";

    if (x == 0)
        sol.push_back('0');

    while (x > 0)
    {
        sol.push_back((x % 2) + '0');
        x /= 2;
    }

    while (sol.size() < 21)
        sol.push_back('0');

    for (int i = 0; i < sol.size() / 2; i++)
        swap(sol[i], sol[sol.size() - 1 - i]);

    return sol;
}

int main()
{
    ifstream in("xormax.in");
    ofstream out("xormax.out");

    ios_base::sync_with_stdio(false);
    in.tie(nullptr);

    int n;
    in >> n;

    Trie* trie = new Trie();

    int sol = 0;
    int st = 1;
    int dr = 1;

    trie->adauga(toString(xorPartial[0]), 0);

    for (int i = 1; i <= n; i++)
    {
        int x;
        in >> x;

        xorPartial[i] = xorPartial[i - 1] ^ x;

        int solIndex;
        int maxim = trie->solutie(toString(xorPartial[i]), solIndex);

        trie->adauga(toString(xorPartial[i]), i);

        if (sol < maxim)
        {
            sol = maxim;
            st = solIndex + 1;
            dr = i;
        }
    }

    out << sol << ' ' << st << ' ' << dr << '\n';

    delete trie;

    return 0;
}