Cod sursa(job #3355956)

Utilizator teosimSimzianu Teodora teosim Data 28 mai 2026 01:28:38
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>


using namespace std;

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

struct Node
{
    int orgIndex;
    Node* children[2] {};
    Node() {
        orgIndex = -1;
        for (auto& i : children)
            i = nullptr;
    }
};

class Trie {
    Node* root;

    static void clear(Node* node)
    {
        if (node == nullptr)
            return;
        for (const auto& i : node->children)
            if (i != nullptr)
                clear(i);
        delete node;
    }

public:

    Trie() {
        root = new Node();
    }

    ~Trie() {
        clear(root);
    }

    void insert(int value, int index) const
    {
        Node* currNode = root;
        for (int i = 20; i >= 0; --i) {
            const int bit = (value >> i) & 1;
            if (currNode->children[bit] == nullptr)
                currNode->children[bit] = new Node();

            currNode = currNode->children[bit];
        }
        currNode->orgIndex = index;
    }

    int query(int value) const
    {
        Node* currNode = root;
        for (int i = 20; i >= 0; i--)
        {
            int bit = (value >> i) & 1;
            int oppositeBit = 1 - bit;

            if (currNode->children[oppositeBit] != nullptr)
                currNode = currNode->children[oppositeBit];

            else
                currNode = currNode->children[bit];
        }
        return currNode->orgIndex;
    }
};

int main() {

    int n;
    fin >> n;
    vector<int> prefix(n + 1, 0);

    Trie trie;
    trie.insert(0, 0);

    int maxXor = -1;
    int bestStart = 0;
    int bestEnd = 0;

    for (int i = 1; i <= n; i++)
    {
        int val;
        fin >> val;

        prefix[i] = prefix[i - 1] ^ val;
        int bestPrevIndex = trie.query(prefix[i]);
        int currentXor = prefix[i] ^ prefix[bestPrevIndex];

        if (currentXor > maxXor)
        {
            maxXor = currentXor;
            bestStart = bestPrevIndex + 1;
            bestEnd = i;
        }
        trie.insert(prefix[i], i);
    }

    fout << maxXor << " " << bestStart << " " << bestEnd << "\n";
    return 0;
}