Pagini recente » Cod sursa (job #1869099) | Cod sursa (job #693985) | Cod sursa (job #471053) | Cod sursa (job #1789897) | Cod sursa (job #1922153)
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int MAX = 1e5 + 5;
int maxx, s[MAX], n, maxi = 1, maxj = 1, max_sum;
struct Trie {
int index;
Trie* f[2];
Trie() {
f[0] = NULL;
f[1] = NULL;
index = 0;
}
};
Trie * root = new Trie();
void add_sum(Trie* nod, int sum, int poz, int i) {
if (poz == -1) {
nod -> index = i;
return;
}
int bit = ((1 << poz) & sum ? 1 : 0);
if (nod -> f[bit] == NULL)
nod -> f[bit] = new Trie();
add_sum(nod -> f[bit], sum, poz - 1, i);
}
int xor_max(Trie* nod, int sum, int poz, int& maxx) {
if (poz == -1)
return nod -> index;
int bit = ((1 << poz) & sum ? 0 : 1);
if (nod -> f[bit] != NULL)
maxx = ((1 << poz) ^ maxx);
else
bit = (bit ? 0 : 1);
xor_max(nod -> f[bit], sum, poz - 1, maxx);
}
int main() {
fin >> n;
for (int temp, nr, i = 1; i <= n; i++) {
fin >> nr;
s[i] = s[i - 1] ^ nr;
add_sum(root, s[i], 20, i);
maxx = 0;
temp = xor_max(root, s[i], 20, maxx);
if (maxx > max_sum) {
max_sum = maxx;
maxi = temp + 1;
maxj = i;
}
}
fout << max_sum << ' ' << maxi << ' ' << maxj;
return 0;
}