Pagini recente » Cod sursa (job #1882674) | Cod sursa (job #1463743) | Cod sursa (job #1020046) | Cod sursa (job #1584401) | Cod sursa (job #2104880)
#include <fstream>
#include <cstring>
#define MAXN 100005
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie{
int bg, cnt;
trie *son[2];
trie() {
bg = cnt = 0;
memset(son, 0, sizeof(son));
}
};
trie *root = new trie();
int N, nn, v[MAXN], x[MAXN], val, sol = 0, in, sf, stop;
int auxiliar;
inline void Read() {
fin >> N;
int maxim = 0;
for (int i = 1; i <= N; i++) {
fin >> v[i];
maxim = max(v[i], maxim);
}
while (maxim) {
maxim /= 2;
nn++;
}
}
inline void Add(trie *node, int poz) {
if (poz > nn) { ///daca am ajuns la sj reprezentarii binare
node->bg = stop;
node->cnt = val;
return;
}
if (node->son[x[poz]] == NULL) {
node->son[x[poz]] = new trie();
}
Add(node->son[x[poz]], poz + 1);
}
inline void Test(trie *node, int poz) {
if (poz > nn + 1) ///daca s-a terminat sirul
return;
int delta = !x[poz];
if (node->cnt > 0) {
auxiliar = (node->cnt ^ val);
if (auxiliar > sol) {
sol = auxiliar;
in = node->bg + 1;
sf = stop;
}
else if (auxiliar == sol && sf == stop) {
if (sf - in + 1 > stop - node->bg)
sf = stop,
in = node->bg;
}
}
if (node->son[delta] == NULL) {
Test(node->son[!delta], poz + 1);
}
else {
Test(node->son[delta], poz + 1);
}
}
inline void Adauga() {
int aux, j;
for (int i = 1; i <= N; i++) {
if (v[i] > sol) {
sol = v[i];
in = i;
sf = i;
}
aux = v[i]; j = nn; stop = i;
val = val ^ v[i];
while (aux) {
x[j] = (x[j] ^ (aux % 2));
aux /= 2;
j--;
}
Add(root, 1);
Test(root, 1);
}
fout << sol << " " << in << " " << sf;
}
int main () {
Read();
Adauga();
fin.close(); fout.close(); return 0;
}