Pagini recente » Cod sursa (job #1713972) | Atasamentele paginii Profil Georginsky | Cod sursa (job #1937921) | Cod sursa (job #1552139) | Cod sursa (job #1515226)
#include <fstream>
#include <algorithm>
using namespace std;
const int kMaxCells = 2100000 + 1;
/* alocare de la 1, caci 0 semnifica NULL */
int Trie[kMaxCells][2], nxt = 1;
int seqPos[kMaxCells];
/* suma xor x la pozitia pos */
inline void emplace(int x, int pos) {
int node = 0;
// de la cel mai semnificativ bit in jos
for (register int i = 21; i >= 0; i--) {
// daca nodul nu exista, il creeaza
if (Trie[node][(x >> i) & 1] == 0) {
Trie[node][(x >> i) & 1] = nxt++;
}
node = Trie[node][(x >> i) & 1];
}
seqPos[node] = pos; // retine pozitia pentru nodul final
}
/* first va contine max, iar second pozitia */
inline pair <int, int> getMax(int x) {
int node = 0, ans = 0;
for (register int i = 21; i >= 0; i--) {
/* 1^0 = 1 | 0^1 = 1, pentru a maximiza xor-ul
continuam pe bitul diferit, daca se poate */
if (Trie[node][~(x >> i) & 1] != 0) {
ans |= (1 << i);
node = Trie[node][~(x >> i) & 1];
} else {
node = Trie[node][(x >> i) & 1];
}
}
return make_pair(ans, seqPos[node]);
}
int main(void) {
ifstream in("xormax.in");
ofstream out("xormax.out");
in.tie(0);
ios_base::sync_with_stdio(0);
int n;
int xorSum, x;
int CET, posStart, posEnd;
in >> n;
CET = -1;
xorSum = 0; // suma xor curenta
emplace(0, -1); // in caz de secventa [1 .. x]
/* a xor 0 = a, a xor a = 0 */
for (register int i = 0; i < n; i++) {
in >> x;
xorSum ^= x;
pair <int, int> q = getMax(xorSum);
if (q.first > CET) {
CET = q.first;
posStart = q.second + 1;
posEnd = i;
}
emplace(xorSum, i);
}
in.close();
out << CET << ' ' << posStart + 1 << ' ' << posEnd + 1 << '\n';
out.close();
return 0;
}