Pagini recente » Cod sursa (job #2373043) | Cod sursa (job #1623318) | Cod sursa (job #2023380) | Cod sursa (job #3183487) | Cod sursa (job #1757321)
#include <bits/stdc++.h>
#define NMAX 100005
#define MAX_NR_BITS 21
using namespace std;
struct Trie{
Trie* node[2];
int end_pos;
Trie(){
node[0] = node[1] = NULL;
end_pos = 0;
}
void Insert(int x, int pos){
Trie* current = this;
for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
int next = ((x & bit) != 0);
if (current->node[next] != NULL) current = current->node[next];
else current = current->node[next] = new Trie;
}
current->end_pos = pos;
}
pair<int, int> Search(int x){
Trie* current = this;
int answer = 0;
for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
int next = ((x & bit) != 0);
if (current->node[next] == NULL) next = 1 - next;
current = current->node[next];
answer |= bit * next;
}
return make_pair(answer, current->end_pos);
}
};
int main()
{
#define USE_FILES
#ifdef USE_FILES
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define cin fin
#define cout fout
#endif // USE_FILES
int n, x, xormax;
int start = 0, stop = 0;
cin >> n;
x = 0;
xormax = 0;
Trie* root = new Trie;
for (int i = 0; i < n; ++i){
int new_x;
cin >> new_x;
x ^= new_x;
root->Insert(x, i);
pair<int, int> answer = root->Search(~x);
if ((x ^ answer.first) > xormax){
xormax = x ^ answer.first;
start = answer.second + 2;
stop = i + 1;
}
}
cout << xormax << ' ' << start << ' ' << stop << '\n';
return 0;
}