Pagini recente » Cod sursa (job #656110) | Cod sursa (job #609606) | Cod sursa (job #2209160) | Cod sursa (job #1976179) | Cod sursa (job #3235178)
#include <bits/stdc++.h>
using namespace std;
const int ALPHA = 2;
const int MAX = 1e5;
int N;
long long A[MAX + 3];
int step;
int l, r;
int leftaux;
string matching;
struct Trie{
struct Node{
int cnt;
Node *next[ALPHA];
Node() {
cnt = 0;
for(int i = 0; i < ALPHA; i++) {
next[i] = NULL;
}
}
};
Node *root;
Trie() {
root = new Node;
}
void insert(string &s) {
Node *curr = root;
for(auto it : s) {
//cout << it << ' ';
if(curr->next[it - '0'] == NULL) {
curr->next[it - '0'] = new Node;
}
curr = curr->next[it - '0'];
}
//cout << '\n';
curr->cnt = step;
}
void find(string &s) {
Node *curr = root;
for(int it = 0; it < s.size(); it++) {
if(curr->next[!(s[it] - '0')] != NULL) {
curr = curr->next[!(s[it] - '0')];
matching.push_back((!(s[it] - '0')) + '0');
//cout << (char)((!(s[it] - '0')) + '0') << ' ';
}
else {
curr = curr->next[s[it] - '0'];
//cout << s[it] << ' ';
matching.push_back(s[it]);
}
}
leftaux = curr->cnt;
}
}T;
string s;
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
cin >> N;
for(int i = 0; i <= 63; i++) {
s.push_back('0');
}
T.insert(s);
long long ans = 0;
long long xorr = 0;
for(int i = 1; i <= N; i++) {
step = i;
cin >> A[i];
xorr = xorr xor A[i];
s.clear();
for(int j = 63; j >= 0; j--) {
if((xorr & (1LL * 1 << j)))
s.push_back('1');
else s.push_back('0');
}
T.find(s);
long long aux = 0;
int jj = 0;
for(int j = 63; j >= 0; j--) {
if(matching[j] == '1') {
aux += (1LL * 1 << jj);
}
jj++;
}
//cout << matching << '\n';
// for(auto it : s) {
// cout << it << ' ';
// }
//cout << '\n';
T.insert(s);
//cout << aux << ' ' << (aux ^ xorr) << '\n';
if(ans < (aux ^ xorr)) {
ans = (aux ^ xorr);
l = leftaux;
r = i;
}
matching.clear();
}
cout << ans << ' ' << l + 1 << ' ' << r;
}