Cod sursa(job #3353901)

Utilizator fanceapaMosul Tudor fanceapa Data 12 mai 2026 14:15:42
Problema Xor Max Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <fstream>
#include <vector>

using namespace std;

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

class Trie {
    Node* root;
    void clear(Node* node) {
        if (node == nullptr) return;
        for (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) {
        Node* currNode = root;
        for (int i = 30; i >= 0; --i) {
            int bit = (value >> i) & 1;
            if (currNode->children[bit] == nullptr)
                currNode->children[bit] = new Node();

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

    int query(int value) const
    {
        Node* currNode = root;
        for (int i = 30; 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->originalIndex;
    }
};

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

    int N;
    fin >> N;

    vector<int> values(N + 1);
    vector<int> prefix(N + 1, 0);

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

    int maxXor = -1;
    int bestStart = 0;
    int bestEnd = 0;
    int bestLen = N + 2;

    for (int i = 1; i <= N; i++) {
        fin >> values[i];
        prefix[i] = prefix[i - 1] ^ values[i];

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

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

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