Cod sursa(job #3308933)

Utilizator CatalinPangaleanuCatalin Pangaleanu CatalinPangaleanu Data 30 august 2025 00:48:47
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <bitset>

struct TrieNode
{
    int index;
    TrieNode *nextTrieNode[2] = {};
};

void insertInTrie(TrieNode *root, int value, int currentIndex)
{
    for (int position = 20; position >= 0; --position)
    {
        int bit = (value >> position) & 1;

        if (root -> nextTrieNode[bit] == nullptr)
            root -> nextTrieNode[bit] = new TrieNode;

        root = root -> nextTrieNode[bit];
    }

    root -> index = currentIndex;
}

std::pair<int, int> getBestPrefix(TrieNode *root, int value)
{
    std::pair<int, int> answer = {};

    for (int position = 20; position >= 0; --position)
    {
        int bit = (value >> position) & 1;
        int want = 1 ^ bit;

        if (root -> nextTrieNode[want])
        {
            answer.first |= 1 << position;

            root = root -> nextTrieNode[want];
        }
        else
        {
            root = root -> nextTrieNode[bit];
        }
    }

    answer.second = root -> index;

    return answer;
}

int main()
{
    std::ifstream inFile;
    inFile.open("xormax.in");

    int n;
    inFile >> n;

    TrieNode *root = new TrieNode;
    insertInTrie(root, 0, 0);

    int currentXor = 0, answer = -1, left = 1, right = 1;

    for (int i = 1; i <= n; ++i)
    {
        int value;
        inFile >> value;

        currentXor ^= value;

        std::pair<int, int> result = getBestPrefix(root, currentXor);

        if (result.first > answer)
        {
            answer = result.first;
            left = result.second + 1;
            right = i;
        }

        insertInTrie(root, currentXor, i);
    }

    inFile.close();

    std::ofstream outFile;
    outFile.open("xormax.out");

    outFile << answer << ' ' << left << ' ' << right;

    outFile.close();

    return 0;
}