Cod sursa(job #3353904)

Utilizator fanceapaMosul Tudor fanceapa Data 12 mai 2026 14:28:27
Problema Xor Max Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 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;

    static 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 = 20; 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 = 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->originalIndex;
    }
};

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

    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;
    int bestLen = N + 2;

    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];
        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;
}