Pagini recente » Cod sursa (job #1072343) | Cod sursa (job #1350630) | Cod sursa (job #3208738) | Cod sursa (job #2909541) | Cod sursa (job #2104911)
#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;
///fie xi = v1 ^ v2 ^...^vi si xj = v1^v2^...^vj
///atunci xi ^ xj = (v[j + 1] ^ v[j + 2]^...^v[i]);
///a^b^a = b pentru ca a ^ a = 0 mereu
///astfel, pentru fiecare x[i] determinat caut x[j] calculat anterior astfel incat xi ^ xj sa fie maxim
///stiind ca a ^ b e 1 doar cand a != b(unde a, b apartin multimii {0, 1}), pentru fiecare cifra binara din x[i] incercam sa mergem pe opusa ei
///astfel, daca xi[k] = e 1, atunci incercam sa mergem pe 0 in trie pentru a obtine o valoare cat mai mare(unde xi[1] = cel mai semnificativ bit)
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 sf 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 + 1;
}
}
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];
if (val > sol) {
sol = val;
in = 1;
sf = 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;
}