Pagini recente » Cod sursa (job #1109366) | Cod sursa (job #649643) | Cod sursa (job #688908) | Cod sursa (job #757393) | Cod sursa (job #3353902)
#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;
}