Pagini recente » Cod sursa (job #2236697) | Cod sursa (job #1959953) | Cod sursa (job #1292249) | Cod sursa (job #329097) | Cod sursa (job #2105004)
///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)
#include <fstream>
#define MAXN 100005
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct TRIE{
int val;
TRIE *son[2];
TRIE()
{
val = 0;
son[0] = son[1] = NULL;
}
};
TRIE *root = new TRIE();
int s[MAXN];
inline void Add(TRIE *NODE, int p, int num, int poz) {
if (p == -1) {
NODE->val = poz;
return;
}
bool bit = (num & (1 << p)); ///testez daca bitul la care am ajuns e 1 sau 0
if (NODE->son[bit] == NULL) {
NODE->son[bit] = new TRIE();
}
Add(NODE->son[bit], p - 1, num, poz);
}
inline int Search(TRIE *NODE, int p, int num) {
if (p == -1)
return NODE->val;
bool bit = (num & (1 << p));
if (NODE->son[!bit] == NULL)
return Search(NODE->son[bit], p - 1, num);
return Search(NODE->son[!bit], p - 1, num);
}
inline void Read() {
int sol = -1, in = 0, sf = 0, N, nr, poz;
fin >> N;
Add(root, 21, 0, 0); ///il adaug pe 0 - pentru a obtine si solutia 1...i
for (int i = 1; i <= N; i++) {
fin >> nr;
s[i] = s[i - 1] ^ nr;
Add(root, 21, s[i], i);
poz = Search(root, 21, s[i]);
if ((s[poz] ^ s[i]) > sol) {
sol = s[poz] ^ s[i];
in = poz + 1;
sf = i;
}
}
fout << sol << " " << in << " " << sf;
}
int main () {
Read();
fin.close(); fout.close(); return 0;
}