Pagini recente » Cod sursa (job #1689877) | Cod sursa (job #678641) | Cod sursa (job #2834223) | Cod sursa (job #488155) | Cod sursa (job #3125084)
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define NMAX (int)(2e5)
#define INF (int)(1e9)
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {cerr << '{'; __print(std::get<0>(x)); cerr << ','; __print(std::get<1>(x)); cerr << ','; __print(std::get<2>(x)); cerr << '}';}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
ordered_set<int> st; // Policy-based DS https://codeforces.com/blog/entry/11080
struct Trie {
Trie* zero;
Trie* one;
int pos;
};
int T, N;
vector<int> v;
int R = 0;
int mx = -1, start = -1, stop = -1;
void add(int x, Trie* trie, int i) {
Trie* walk = trie;
for (int i = 31; i >= 0; --i) {
bool bit = ((x >> i) & 1);
if (bit) {
if (!walk->one)
walk->one = new Trie();
walk = walk->one;
} else {
if (!walk->zero)
walk->zero = new Trie();
walk = walk->zero;
}
}
walk->pos = i;
return;
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
cin >> N;
v = vector<int>(N);
for (int i = 0; i < N; ++i)
cin >> v[i];
Trie* trie = new Trie();
add(0, trie, -1);
for (int i = 0; i < N; ++i) {
const int& el = v[i];
R ^= el;
int x = 0;
Trie* walk = trie;
for (int j = 31; j >= 0; --j) { // go through the bits of §x§ from MSB to LSB
bool bit = ((el >> j) & 1); // true, of el has bit of 1 on pos "i"
if (bit) {
if (walk->zero) {
walk = walk->zero;
} else {
x |= (1 << j); // keep "1" on pos "i"
walk = walk->one;
}
}
else {
if (walk->one) {
walk = walk->one;
x |= (1 << j);
} else {
walk = walk->zero;
}
}
}
int cand = R ^ x;
if (cand > mx) {
mx = cand;
start = walk->pos + 1;
stop = i;
}
add(R, trie, i);
}
cout << mx << ' ' << start + 1 << ' ' << stop + 1 << '\n'; // 1-indexed
return 0;
}