Pagini recente » Cod sursa (job #1240284) | Cod sursa (job #2425972) | Cod sursa (job #1120383) | Cod sursa (job #834201) | Cod sursa (job #1110746)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
const int NMAX = 100009;
const int MAXBIT = 22;
int N; int V[NMAX]; int res; int best_mask; int best_dr; int best = -(1<<30); int best_st;
class Trie {
public:
Trie *son[2];
Trie() {
memset(son, 0, sizeof(son));
}
};
Trie* T = new Trie;
void init(Trie *X, int pos) {
if(pos == -1) return;
X -> son[0] = new Trie;
init(X -> son[0], pos - 1);
}
void add(Trie *X, const int &value, int pos) {
if(pos == -1) {
return ;
}
int bit = (((1 << pos) & value) == (1 << pos));
if(X -> son[bit] == 0) {
X -> son[bit] = new Trie;
}
add(X -> son[bit], value, pos - 1);
}
void search(Trie* X, const int& value, int pos) {
if(pos == -1) return ;
int bit = ( (value & (1 << pos)) == (1 << pos));
if(X -> son[bit]){
res = (res << 1) + bit;
search(X -> son[bit], value, pos - 1);
return;
}
if(X -> son[(bit + 1) % 2]) {
res = (res << 1) + ( (bit + 1) % 2 );
search(X -> son[(bit + 1) % 2], value, pos - 1);
return;
}
return;
}
int main() {
int mask = 0;
fin >> N;
init(T, MAXBIT);
for(int i = 1; i <= N; ++i) {
int value;
fin >> value; V[i] = value;
mask ^= value; res = 0;
int tofind = mask ^ ( (1 << MAXBIT) - 1);
search(T, tofind, MAXBIT);
add(T, mask ,MAXBIT);
int v = res ^ mask;
if(v > best) {
best_mask = res;
best_dr = i;
best = v;
}
}
mask = 0;
for(int i = 1; i <= best_dr; ++i) {
if(mask == best_mask)
best_st = i;
mask ^= V[i];
}
fout << best << " " << best_st << " " << best_dr <<'\n';
return 0;
}