Pagini recente » Cod sursa (job #2619337) | Cod sursa (job #643899) | Cod sursa (job #1695155) | Cod sursa (job #2833421) | Cod sursa (job #1498581)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int lmax= 2097162;
int nodes= 1;
int pos[lmax+1], nr[lmax+1];
vector <int> v[lmax+1];
void newnode( int x) {
for ( int i= 20, node= 0; i>=0; --i ) {
int bit= 0;
if ( (x&(1<<i))>0 ) {
bit= 1;
}
if ( (int)v[node].size()==0 || ((int)v[node].size()==1 && nr[v[node][0]]!=bit) ) {
++nodes;
v[node].push_back(nodes);
nr[nodes]= bit;
node= nodes;
} else {
if ( nr[v[node][0]]==bit ) {
node= v[node][0];
} else {
node= v[node][1];
}
}
}
}
int find_best( int x ) {
int sol= 0;
for ( int i= 20, node= 0; i>=0; --i ) {
int bit= 0;
if ( (x&(1<<i))>0 ) {
bit= 1;
}
int ok= 0;
for ( int j= 0; j<(int)v[node].size(); ++j ) {
if ( nr[v[node][j]]!=bit ) {
ok= 1;
node= v[node][j];
sol= sol+(1-bit)*(1<<i);
}
}
if ( ok==0 ) {
node= v[node][0];
sol= sol+bit*(1<<i);
}
}
return sol;
}
int main( ) {
int n, sol= 0, start= 0, stop= 0;
fin>>n;
for ( int i= 1, x, aux= 0; i<=n; ++i ) {
fin>>x;
aux^= x;
if ( i==1 ) {
sol= aux;
start= stop= 1;
} else {
int k= find_best(aux);
if ( k^aux>sol ) {
sol= k^aux;
start= pos[k]+1;
stop= i;
}
}
newnode(aux);
pos[aux]= i;
}
fout<<sol<<" "<<start<<" "<<stop<<"\n";
return 0;
}