Pagini recente » Cod sursa (job #738118) | Cod sursa (job #2370259) | Cod sursa (job #2050345) | Cod sursa (job #495302) | Cod sursa (job #947376)
Cod sursa(job #947376)
#include<fstream>
#include<vector>
#define left l
#define right r
using namespace std;
class node{
public:
node(){
zero = 0;
one = 0;
}
node(int z1, int o1){
zero = z1;
one = o1;
}
friend void update(int x);
friend int query(int x);
private:
int zero, one;
};
vector<node> t;
int p = 0;
void update(int x){
if(t.empty())
t.push_back(node());
int now = 0;
for(int i = 20; i >= 0; --i)
if(x & (1 << i)){
if(t[now].one == 0){
t[now].one = ++p;
t.push_back(node());
now = p;
}
else
now = t[now].one;
}
else{
if(t[now].zero == 0){
t[now].zero = ++p;
t.push_back(node());
now = p;
}
else
now = t[now].zero;
}
}
int query(int x){
int now = 0, y = 0;
for(int i = 20; i >= 0; --i)
if(x & (1 << i)){
if(t[now].zero == 0){
y += 1 << i;
now = t[now].one;
}
else
now = t[now].zero;
}
else{
if(t[now].one == 0)
now = t[now].zero;
else{
y += 1 << i;
now = t[now].one;
}
}
return x ^ y;
}
int n, ans = -1, l, r, num[100005], pxor[100005];
void read(){
ifstream in("xormax.in");
in >> n;
for(int i = 1; i <= n; ++i){
in >> num[i];
pxor[i] = pxor[i - 1] ^ num[i];
}
}
void solve(){
int changed = 0;
for(int i = 0; i <= n; ++i){
update(pxor[i]);
int pans = query(pxor[i]);
if(pans > ans){
ans = pans;
changed = i;
}
}
if(changed)
for(int i = changed - 1; i > 0; --i)
if((pxor[i] ^ pxor[changed]) == ans){
left = i + 1;
right = changed;
break;
}
}
void write(){
ofstream out("xormax.out");
out << ans << " " << left << " " << right;
}
int main(){
read();
solve();
write();
return 0;
}