Pagini recente » Cod sursa (job #3334146) | Cod sursa (job #3356823) | Monitorul de evaluare | Cod sursa (job #3349227) | Cod sursa (job #3351220)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <chrono>
#include <numeric>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <string.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
#define M 1000000007
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
// auto lim=unique(all(v));
// v.resize(distance(v.begin(), lim));
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct pair_custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
auto hash1 = splitmix64(p.first+FIXED_RANDOM);
auto hash2 = splitmix64(p.second+FIXED_RANDOM);
return hash1^hash2;
}
};
ll gcd(ll a,ll b){
ll r;
while(b){
r=a%b;
a=b;
b=r;
}
return a;
}
ll lcm(ll a,ll b){
return a*b/gcd(a,b);
}
template<class T> T nxt() {
T x;
cin >> x;
return x;
}
class TrieNode{
public:
TrieNode* children[2];
int pos;
TrieNode(){
pos=-1;
memset( children, 0, sizeof( children ) );
}
};
void insertValue(TrieNode* root,const int& x,const int& pos){
TrieNode* currentNode=root;
for(int i=30;i>=0;--i){
int position=bool((x&(1<<i)));
if(currentNode->children[position]==nullptr){
// Create a new node
currentNode->children[position]=new TrieNode();
}
currentNode=(currentNode->children[position]);
}
currentNode->pos=pos;
}
pair<int,int> getMaximumXorValue(TrieNode* root,const int& x){
TrieNode* currentNode=root;
int y=0;
for(int i=30;i>=0;--i){
int position=1-bool(x&(1<<i));
if(currentNode->children[position]==nullptr){
position=1-position;
}
y+=position*(1<<i);
currentNode=(currentNode->children[position]);
}
return {y,currentNode->pos};
}
void Solve(){
int n;
cin>>n;
vi v(n);
generate(all(v),nxt<int>);
TrieNode* root=new TrieNode();
insertValue(root,0,-1);
int x=0,ans=0,l=-1,r=-1;
for(int i=0;i<n;++i){
x^=v[i];
int y,ypos;
tie(y,ypos)=getMaximumXorValue(root,x);
int mval=x^y;
if(mval>ans){
ans=mval;
r=i+1;
l=ypos+2;
}
insertValue(root,x,i);
}
cout<<ans<<' '<<l<<' '<<r<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
Solve();
return 0;
}