Pagini recente » Cod sursa (job #1492671) | Cod sursa (job #1236765) | Cod sursa (job #2454893) | Cod sursa (job #2865267) | Cod sursa (job #2217628)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 100000;
const int BITS = 21;
const int MAX_VAL = (1 << BITS) - 1;
struct TrieNode {
TrieNode* sons[2];
int ind;
TrieNode() {
sons[0] = sons[1] = NULL;
ind = 0;
}
};
TrieNode* Root = new TrieNode();
int n;
int v[1 + N_MAX];
int xp[1 + N_MAX];
int xormax = -1, startmax, stopmax;
void trieInsert(TrieNode* Node, const int nr, const int index)
{
for (int bit = BITS - 1; bit >= 0; bit--) {
if (Node->sons[(nr >> bit) & 1] == NULL)
Node->sons[(nr >> bit) & 1] = new TrieNode();
Node = Node->sons[(nr >> bit) & 1];
}
Node->ind = index;
}
int trieQuery(TrieNode* Node, const int nr)
{
for (int bit = BITS - 1; bit >= 0; bit--) {
if (Node->sons[(nr >> bit) & 1] != NULL)
Node = Node->sons[( nr >> bit) & 1];
else
Node = Node->sons[(~nr >> bit) & 1];
}
return Node->ind;
}
int main() {
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
fin >> n;
xp[0] = 0;
for(int i = 1; i <= n; i++) {
fin >> v[i];
xp[i] = xp[i - 1] ^ v[i];
}
trieInsert(Root, xp[0], 0);
for(int i = 1; i <= n; i++) {
int xorComp = MAX_VAL ^ xp[i];
int j = trieQuery(Root, xorComp);
int Xor = xp[i] ^ xp[j];
if(Xor > xormax)
{
xormax = Xor;
startmax = j + 1;
stopmax = i;
}
trieInsert(Root, xp[i], i);
}
fout << xormax << " " << startmax << " " << stopmax << '\n';
return 0;
}