Pagini recente » Cod sursa (job #1581002) | Cod sursa (job #2555553) | Cod sursa (job #2562377) | Cod sursa (job #2555299) | Cod sursa (job #1110601)
#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;
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) {
mask ^= V[i];
if(mask == best_mask) {
fout << best << " " << i + 1 <<" " << best_dr <<'\n';
break;
}
}
return 0;
}