Pagini recente » Cod sursa (job #99617) | Cod sursa (job #2171257) | Cod sursa (job #1925432) | Cod sursa (job #243152) | Cod sursa (job #2565395)
#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
#ifdef DEBUG
string name = "data";
#else
string name = "xormax";
#endif
ifstream fin(name + ".in");
ofstream fout(name + ".out");
class Trie {
public:
Trie *children[2];
int index;
void insert(int bit, int x, int index) {
if (bit == -1) {
this->index = index;
return;
}
bool val = (x & (1 << bit)) > 0;
if (children[val] == NULL) {
children[val] = new Trie();
}
children[val]->insert(bit - 1, x, index);
}
pair<int, int> findBest(int bit, int x) {
if (bit == -1) {
return {0, index};
}
bool val = (x & (1 << bit)) > 0;
pair<int, int> res;
if (children[!val] != NULL) {
res = children[!val]->findBest(bit - 1, x);
res.first += (1 << bit);
} else {
res = children[val]->findBest(bit - 1, x);
}
return res;
}
};
Trie trie;
int maxBit = 21;
int n;
int main() {
trie.insert(maxBit, 0, 0);
int s = 0;
int best = 0;
int start = 0;
int end = 0;
fin >> n;
for (int i = 0; i < n; ++i) {
int x;
fin >> x;
s ^= x;
auto candidate = trie.findBest(maxBit, s);
if (candidate.first > best) {
best = candidate.first;
end = i + 1;
start = candidate.second + 1;
}
trie.insert(maxBit, s, i + 1);
}
fout << best << " " << start << " " << end;
return 0;
}