Cod sursa(job #3353902)

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

using namespace std;

// The problem states values are < 2^21, which means bit 20 is the highest bit needed.
const int MAX_BITS = 20;
// 100,000 numbers * 21 bits = roughly 2,100,000 max nodes
const int MAX_NODES = 2100005;

// Static Arrays replace the dynamically allocated 'Node' struct
int trie[MAX_NODES][2];
int leafIndex[MAX_NODES];
int nodeCount = 0;

void insert(int value, int idx) {
    int curr = 0; // 0 represents the root of the Trie
    for (int i = MAX_BITS; i >= 0; --i) {
        int bit = (value >> i) & 1;
        // If the path doesn't exist, create it
        if (trie[curr][bit] == 0) {
            trie[curr][bit] = ++nodeCount;
        }
        curr = trie[curr][bit];
    }
    // Overwriting the leaf with the LATEST index is mathematically brilliant.
    // It guarantees that among identical prefixes, we always get the SHORTEST subarray.
    leafIndex[curr] = idx;
}

int query(int value) {
    int curr = 0;
    for (int i = MAX_BITS; i >= 0; --i) {
        int bit = (value >> i) & 1;
        int oppositeBit = 1 - bit;

        // Greedy choice: Opposites attract in XOR. Try to go down the opposite path.
        if (trie[curr][oppositeBit] != 0) {
            curr = trie[curr][oppositeBit];
        } else {
            curr = trie[curr][bit];
        }
    }
    return leafIndex[curr];
}

int main() {
    // Fast I/O is mandatory to read 100,000 numbers inside a 0.1s time limit
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!freopen("xormax.in", "r", stdin)) return 0;
    if (!freopen("xormax.out", "w", stdout)) return 0;

    int N;
    if (!(cin >> N)) return 0;

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

    // Insert the base case so a subarray can start exactly at the first element
    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;
        cin >> val;
        prefix[i] = prefix[i - 1] ^ val;

        int bestPrevIndex = 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) {
            // Tie-breaker: We ONLY update if the length is strictly less.
            // If the lengths are identical, your code correctly ignores the new one,
            // naturally preserving the earlier start index!
            if (currentLen < bestLen) {
                bestStart = bestPrevIndex + 1;
                bestEnd = i;
                bestLen = currentLen;
            }
        }

        insert(prefix[i], i);
    }

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