Pagini recente » Cod sursa (job #192861) | Cod sursa (job #1813476) | Cod sursa (job #579977) | Cod sursa (job #1599243) | Cod sursa (job #1757587)
#include <bits/stdc++.h>
#define NMAX 100005
#define MAX_NR_BITS 20
using namespace std;
int trie[(1 << MAX_NR_BITS + 3)];
void Insert(int x, int pos){
int node = 1;
for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
int next = ((x & bit) != 0);
node = (node << 1) | next;
trie[node] = pos;
}
}
int Search(int x){
int node = 1;
int answer = 0;
for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
int next = ((x & bit) != 0);
if (trie[(node << 1) | next] == 0) next = 1 - next;
node = (node << 1) | next;
answer |= bit * next;
}
return answer;
}
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, xorsum, xormax;
int start = 0, stop = 0;
cin >> n;
xorsum = 0;
xormax = -1;
Insert(0, 1);
for (int i = 0; i < n; ++i){
int x;
cin >> x;
xorsum ^= x;
/// Search
x = ~xorsum;
int node = 1;
int answer = 0;
for (int bit = (1 << MAX_NR_BITS); bit > 0; bit >>= 1){
int next = ((x & bit) != 0);
if (trie[(node << 1) | next] == 0) next = next ^ 1;
node = (node << 1) | next;
answer |= bit * next;
}
if ((xorsum ^ answer) > xormax){
xormax = xorsum ^ answer;
start = trie[node];
stop = i + 1;
}
Insert(xorsum, i + 2);
}
cout << xormax << ' ' << start << ' ' << stop << '\n';
return 0;
}