Pagini recente » Cod sursa (job #525851) | Cod sursa (job #1728006) | Cod sursa (job #1710892) | Cod sursa (job #40596) | Cod sursa (job #3255968)
#include <iostream>
#include <fstream>
#include <vector>
//#include <bits/stdc++.h>
#include <algorithm>
#include <iterator>
#define in fin
#define out fout
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct node{
node* v[2]; // pentru copilul care duce 0 si 1
node(){
for(int i = 0; i < 2; i++){
v[i] = NULL;
}
}
};
node* r = new node();
void add(node* nod, string & s, int i){
if(i == s.size()){
return;
}
if( nod->v[ s[i] - '0' ] == NULL ){
nod->v[ s[i] - '0' ] = new node();
}
add( nod->v[ s[i] - '0' ], s, i + 1 );
}
string sol;
void query(node* nod, string & s, int i){
if(i == s.size()){
return;
}
int wanted = 1 - (s[i] - '0');
if(nod->v[ wanted ] == NULL) wanted = 1 - wanted;
if(nod->v[ wanted ] == NULL) return;
sol.push_back( char(wanted + '0') );
query( nod->v[ wanted ], s, i + 1 );
}
string binar(int nr){
string s;
while(nr){
s.push_back( char('0' + nr % 2) );
nr /= 2;
}
while(s.size() < 22) s.push_back('0');
reverse(s.begin(), s.end());
return s;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; in >> n;
int v[n];
for(int i = 0; i < n; i++) in >> v[i];
int xr[n + 1];
xr[0] = 0;
string aa = binar(0);
add(r, aa, 0);
int maxi = INT_MIN;
int v1 = -1, p = 0;
for(int i = 1; i <= n; i++){
xr[i] = (xr[i - 1] ^ v[i - 1]);
sol.clear();
aa = binar( xr[i] );
query(r, aa, 0);
int nr = 0;
for(int i = sol.size() - 1; i >= 0; i--) nr = nr + (1 << (sol.size() - i - 1)) * (sol[i] - '0');
if( (nr ^ xr[i]) > maxi ){
maxi = (nr ^ xr[i]);
p = i;
v1 = nr;
}
// cout << "i = " << i << " maxi = " << maxi << '\n';
add( r, aa, 0 );
}
int p2 = p - 1;
while(p2 > 0 && xr[p2] != v1) p2--;
out << maxi << " " << p2 + 1 << " " << p << '\n';
return 0;
}