Pagini recente » Cod sursa (job #62006) | Cod sursa (job #3262155) | Cod sursa (job #1668329) | Cod sursa (job #2807796) | Cod sursa (job #1468742)
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const string name = "xormax",
in_file = name + ".in",
out_file = name + ".out";
ifstream fin(in_file);
ofstream fout(out_file);
const int MAX = 1e5 + 5;
int maxx, s[MAX], n, maxi, maxj, max_sum;
struct Trie {
int index;
Trie* f[2];
Trie() {
memset(f, 0, sizeof(f));
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;
}