Pagini recente » Cod sursa (job #3279349) | Cod sursa (job #815176) | Cod sursa (job #815301) | Cod sursa (job #2514681) | Cod sursa (job #2767082)
#include <bits/stdc++.h>
#ifdef INFOARENA
#define __OUTPUT_FILE__ fout
#else
#define __OUTPUT_FILE__ std::cout
#endif
#define print(x) __OUTPUT_FILE__ << x
#define read(x) fin >> x
#define debugPrint(x) print(#x << ": " << (x) << '\n')
#define MAXNUMS 100000
#define __NAME_OF_THE_FILE__ "xormax"
typedef unsigned int type;
std::ifstream fin(__NAME_OF_THE_FILE__ ".in");
std::ofstream fout(__NAME_OF_THE_FILE__ ".out");
type n, arr[MAXNUMS + 1];
void setup(), solve(), finish();
const size_t nrBiti = 21;
type max = -1, start, end;
struct Tree {
public:
type index; // leaf node index
Tree *children[2];
Tree() {
index = 0;
children[0] = 0; // the pointer points to an empty address
children[1] = 0; // the pointer points to an empty address
}
// moves through the bits of the val (from the most significative to the
// last significative)
// and adds them to the trie (a suffix trie to be precise)
void insert(type val, type index) {
Tree *node = this;
for (size_t i = 0; i < nrBiti; i++) {
bool bit = val & (1 << ((nrBiti - 1) - i));
if (node->children[bit] == 0) node->children[bit] = new Tree();
node = node->children[bit];
// && node->hasBeenUsed == false // left most start index
if (i == (nrBiti - 1)) {
node->index = index;
}
}
}
// it searches for a number ( [compl] ) for which [compl] ^ [val] is the
// greatast as it can be
// it returns compl->index
type search(type val) {
Tree *node = this;
type index;
for (size_t i = 0; i < nrBiti; i++) {
bool bit = val & (1 << ((nrBiti - 1) - i));
bool invBit = 1 - bit;
if (node->children[invBit] != 0) { // if exists
node = node->children[invBit];
} else {
node = node->children[bit];
}
if (i == (nrBiti - 1)) { // if we are on a leaf
index = node->index;
}
}
return index;
}
} tree;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
setup();
solve();
finish();
return 0;
}
// solve the problem (succes jmechere ;)
void solve() {
for (size_t i = 1; i < n; i++) {
arr[i] ^= arr[i - 1];
if (i > 1) {
type j = tree.search(arr[i]);
type sumxor = arr[j] ^ arr[i];
if (sumxor > max) {
max = sumxor;
start = j + 1;
end = i;
}
}
tree.insert(arr[i], i);
}
}
// read the data from the input file
void setup() {
read(n);
n++;
for (size_t i = 1; i < n; i++) {
read(arr[i]);
}
fin.close();
}
// print the data to the console/file
void finish() {
print(max << ' ' << start << ' ' << end);
fout.close();
}