Pagini recente » Cod sursa (job #3352507) | Cod sursa (job #1004957) | Cod sursa (job #1320944) | Cod sursa (job #1043745) | Cod sursa (job #3352509)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const int SIGMA = 25;
int sp[MAXN + 1];
struct Trie {
struct Node {
int nxt[2] , idx;
} t[MAXN * SIGMA + 1];
int len = 1;
void add( string s , int idx ) {
int u = 1 , c;
for( auto ch : s ) {
c = ch - '0';
//cout << u << ' ' << ch << '\n';
if( !t[u].nxt[c] )
t[u].nxt[c] = ++len;
u = t[u].nxt[c];
}
t[u].idx = idx;
}
pair< int , int >findbest( string s ) {
int ans = 0 , u = 1 , c , i = 20;
for( auto ch : s ) {
c = ch - '0';
if( t[u].nxt[1 - c] ) {
ans += ( 1 << i );
u = t[u].nxt[1 - c];
} else
u = t[u].nxt[c];
i--;
}
return { ans , t[u].idx };
}
} trie;
int main() {
ifstream cin( "xormax.in" );
ofstream cout( "xormax.out" );
int n , i , xorr , x , j , ans , l , r;
string s;
cin >> n;
xorr = ans = 0;
for( i = 1 ; i <= n ; i++ ) {
cin >> x;
// xor de la i la j este xor[i] ^ xor[j - 1]
s = "";
for( j = 20 ; j >= 0 ; j-- )
if( xorr & ( 1 << j ) )
s += "1";
else
s += "0";
trie.add( s , i );
xorr ^= x;
s = "";
for( j = 20 ; j >= 0 ; j-- )
if( xorr & ( 1 << j ) )
s += "1";
else
s += "0";
//cout << xorr << ' ' << s << '\n';
//cout << trie.findbest( s ).first << '\n';
if( ans < trie.findbest( s ).first ) {
ans = trie.findbest( s ).first;
l = trie.findbest( s ).second;
r = i;
}
}
cout << ans << ' ' << l << ' ' << r << '\n';
//cout << ans << '\n';
return 0;
}