Pagini recente » Autentificare | Cod sursa (job #1007007) | Cod sursa (job #1309938) | Cod sursa (job #2023625) | Cod sursa (job #562487)
Cod sursa(job #562487)
#include<fstream>
const int maxn = 100005;
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int i , j , n , sum[maxn] , a , maxs = -1 , lf , rt;
struct Trie {
int mark;
Trie *fiu[2];
Trie() {
mark = 0;
fiu[0] = fiu[1] = 0;
}
};
Trie *T = new Trie;
void insert( Trie *nod , int sum , int ind) {
if (ind == -1) {
nod -> mark = i;
return;
}
bool t = ( sum & (1 << ind));
if ( nod -> fiu[t] == 0 )
nod -> fiu[t] = new Trie;
insert (nod -> fiu[t] , sum , ind - 1);
}
void lookup (int x , int r) {
int i;
Trie *nod = T;
for( i = 21 ; i >= 0 ; --i ) {
bool t = (x & (1 << i));
if ( nod -> fiu[t ^ 1] )
nod = nod -> fiu[t ^ 1];
else
nod = nod -> fiu[t];
}
if ( (x xor sum[nod -> mark]) > maxs ) {
maxs = x xor sum[nod -> mark];
lf = nod -> mark + 1;
rt = r;
}
}
int main()
{
fin >> n;
i = 0;
insert(T , 0 , 21);
for( i = 1 ; i <= n ; ++i ) {
fin >> a;
sum[i] = sum[i - 1] xor a;
lookup(sum[i] , i);
insert(T , sum[i] , 21);
}
fout << maxs <<" " <<lf <<" " << rt << "\n";
return 0;
}