Pagini recente » Cod sursa (job #720588) | Cod sursa (job #2298563) | Cod sursa (job #759296) | Cod sursa (job #642671) | Cod sursa (job #3353970)
/*
* author: qvalentin
* https://codeforces.com/profile/qvalentin
*
* It's you, it'll always be you *
*/
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
const int MOD = 1e9+7;
int di[4]={0,0,-1,1};
int dj[4]={-1,1,0,0};
string FILENAME="xormax";
ifstream f(FILENAME+".in");
ofstream g(FILENAME+".out");
struct Node {
Node* children[2];
int end;
Node() {
for(int i = 0; i < 2; ++i) {
children[i] = nullptr;
}
end = 0;
}
};
class Trie {
private:
Node* root;
public:
Trie(){
root = new Node();
}
void insert(int x, int idx) {
Node* curr = root;
for(int i = 21; i >= 0; --i) {
int bit = (x >> i) & 1;
if(!curr->children[bit])curr->children[bit] = new Node();
curr = curr->children[bit];
}
curr->end = idx;
}
pair<int,int> getMax(int x) {
Node* curr = root;
int best= 0;
for(int i = 21; i >= 0; --i) {
int bit = (x >> i) & 1;
if(curr->children[1-bit]) {
best |= (1 << i);
curr=curr->children[1-bit];
}
else {
curr=curr->children[bit];
}
}
return {best, curr->end + 1};
}
};
signed main(){
fastio
//P0 = 0
//Pi = Pi-1 ^ xi
//Pi ^ Pj max
#ifndef qv
#define cin f
#define cout g
#endif
Trie tr;
tr.insert(0,0);
int n;
cin>>n;
int currP = 0;
int mx = 0;
int st=1,dr=1;
int lmn = -1;
for(int i=1;i<=n;++i) {
int x;
cin>>x;
currP ^= x;
tr.insert(currP,i);
pair<int,int> tmp = tr.getMax(currP);
if(tmp.first > mx) {
mx = tmp.first;
dr = i;
st = tmp.second;
lmn = dr-st+1;
}
else if(tmp.first == mx) {
if(i < dr) {
dr = i;
lmn=dr-st+1;
}
else if(i == dr) {
if(lmn > dr-st+1){
lmn=dr-st+1;
}
}
}
}
cout<<mx<<' '<<st<<' '<<dr;
return 0;
}