Pagini recente » Cod sursa (job #2793751) | Cod sursa (job #2761714) | Cod sursa (job #1111517) | Cod sursa (job #735624) | Cod sursa (job #3217668)
#include <iostream>
#include <fstream>
#include <stdint.h>
const int32_t MAX_N = 100000;
const int32_t MAX_VAL_LOG_2 = 21;
const int32_t MAX_VAL = 1 << MAX_VAL_LOG_2;
struct Node {
int32_t ind;
Node* children[2];
};
int32_t vec[MAX_N + 1];
Node nodes[MAX_VAL];
int32_t top = 0;
Node* tree;
int32_t Find(int32_t val) {
Node* node = tree;
for(int32_t i = MAX_VAL_LOG_2 - 1; i != -1; --i) {
int32_t bit = (val >> i) & 1;
int32_t child = bit ^ 1;
if(!node->children[child])
child ^= 1;
node = node->children[child];
}
return node->ind;
}
void Insert(int32_t val, int32_t ind) {
Node* node = tree;
for(int32_t i = MAX_VAL_LOG_2 - 1; i != -1; --i) {
int32_t bit = (val >> i) & 1;
if(!node->children[bit]) {
Node* newNode = nodes + top;
++top;
node->children[bit] = newNode;
}
node = node->children[bit];
}
node->ind = ind;
}
int main() {
std::ifstream fin("xormax.in");
std::ofstream fout("xormax.out");
int32_t n;
fin >> n;
for(int32_t i = 1; i <= n; ++i)
fin >> vec[i];
for(int32_t i = 2; i <= n; ++i)
vec[i] ^= vec[i - 1];
tree = nodes;
++top;
Insert(0, 0);
Insert(vec[1], 1);
int32_t st = 1, dr = 1, max = vec[1];
for(int32_t i = 2; i <= n; ++i) {
int32_t start = Find(vec[i]);
int32_t val = vec[i] ^ vec[start];
if(val > max) {
st = start + 1;
dr = i;
max = val;
}
Insert(vec[i], i);
}
fout << max << ' ' << st << ' ' << dr;
fin.close();
fout.close();
return 0;
}