Cod sursa(job #2923258)

Utilizator matei.tudoseMatei Tudose matei.tudose Data 12 septembrie 2022 13:26:04
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
using namespace std;

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

int n, xor_partial[100005];

class TrieNode
{
    TrieNode *edges[2];
    int index;

public:
    TrieNode()
    {
        edges[0] = edges[1] = nullptr;
        index = -1;
    }

    void Insert(int num, int inputIndex, int depth)
    {
        if (depth == -1)
        {
            index = inputIndex;
            return;
        }
        int curentBit = ((num >> depth) & 1);
        if (edges[curentBit] == nullptr)
        {
            edges[curentBit] = new TrieNode();
        }
        edges[curentBit]->Insert(num, inputIndex, depth - 1);
    }

    int DFS(int num, int depth = 19)
    {
        if (depth == -1)
        {
            return index;
        }
        int curentBit = ((num >> depth) & 1);
        if (edges[!curentBit] != nullptr)
        {
            return edges[!curentBit]->DFS(num, depth - 1);
        }
        else
        {
            return edges[curentBit]->DFS(num, depth - 1);
        }
    }
};

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        fin >> x;
        xor_partial[i] = xor_partial[i - 1] ^ x;
    }
    TrieNode root = TrieNode();
    root.Insert(xor_partial[1], 1, 19);
    if (n == 1)
    {
        fout << xor_partial[1] << "1 1\n";
        return 0;
    }
    int maxValue = -1;
    int leftAns, rightAns;
    for (int i = 2; i <= n; i++)
    {
        int left = root.DFS(xor_partial[i]);
        int valPosibil = xor_partial[left] ^ xor_partial[i];
        if (xor_partial[i] > valPosibil && xor_partial[i] > maxValue)
        {
            valPosibil = xor_partial[i];
            leftAns = 1;
            rightAns = i;
        }
        else if (valPosibil > maxValue)
        {
            maxValue = valPosibil;
            leftAns = left + 1;
            rightAns = i;
        }
        root.Insert(xor_partial[i], i, 19);
    }
    fout << maxValue << ' ' << leftAns << ' ' << rightAns << '\n';
    return 0;
}