Pagini recente » Cod sursa (job #2625085) | Cod sursa (job #690191) | Cod sursa (job #90880) | Cod sursa (job #2715768) | Cod sursa (job #159936)
Cod sursa(job #159936)
#include <iostream>
#include <fstream>
using namespace std;
#define act ((cur & i) ? (1) : (0))
class Node {
public:
Node() :
idx(0)
{
c[0] = c[1] = 0;
}
Node *c[2];
int idx;
};
int A[100001];
int N;
Node root;
void insert_into_trie(int cur, int idx) {
Node *n = &root;
for (int i = 1 << 30; i > 0; i >>= 1) {
if (!n->c[act])
n->c[act] = new Node;
n = n->c[act];
}
n->idx = idx;
}
int find_in_trie(int cur) {
Node *n = &root;
for (int i = 1 << 30; i > 0; i >>= 1) {
if (n->c[!act]) {
n = n->c[!act];
continue;
}
if (n->c[act]) {
n = n->c[act];
continue;
}
return -1;
}
return n->idx;
}
int main(int argc, char *argv[]) {
FILE *fi = fopen("xormax.in", "r");
fscanf(fi, "%d", &N);
int aux;
insert_into_trie(0, 0);
int largest(-1),
ms, mf;
for (int i(1); i <= N; ++i) {
fscanf(fi, "%d", &aux);
A[i] = A[i-1] ^ aux;
aux = find_in_trie(A[i]);
//cout << A[i] << " " << A[aux] << " (" << aux << ") -> " << (A[i] ^ A[aux]) << endl;
if (aux != -1)
if ((A[i] ^ A[aux]) > largest) {
largest = A[i] ^ A[aux];
ms = aux + 1;
mf = i;
}
//cout << cur << endl;
insert_into_trie(A[i], i);
}
fclose(fi);
ofstream fout("xormax.out");
fout << largest << " " << ms << " " << mf << endl;
fout.close();
return 0;
}