Pagini recente » Cod sursa (job #19496) | Cod sursa (job #860005) | Cod sursa (job #600092) | Cod sursa (job #2280109) | Cod sursa (job #159907)
Cod sursa(job #159907)
#include <iostream>
#include <fstream>
using namespace std;
class Node {
public:
Node() :
left(0),
right(0),
idx(0)
{
}
Node *left, *right;
int idx;
};
int N;
int A[100001];
Node root;
void insert_into_trie(int cur, int idx) {
int i = 1 << 22;
Node *n = &root;
while (i > 0) {
if (i & cur) {
if (!n->right)
n->right = new Node;
n = n->right;
} else {
if (!n->left)
n->left = new Node;
n = n->left;
}
i >>= 1;
}
n->idx = idx;
}
int find_in_trie(int cur) {
int i = 1 << 22;
Node *n = &root;
while (i > 0) {
if (i & cur) {
if (n->left)
n = n->left;
else
n = n->right;
} else {
if (n->right)
n = n->right;
else
n = n->left;
}
i >>= 1;
}
return n->idx;
}
#define MIN(a, b) ((a > b) ? (b) : (a))
#define MAX(a, b) ((a > b) ? (a) : (b))
int main(int argc, char *argv[]) {
FILE *fi = fopen("xormax.in", "r");
fscanf(fi, "%d", &N);
int aux;
int cur(0);
for (int i(0); i < N; ++i) {
fscanf(fi, "%d", &aux);
A[i] = cur ^= aux;
//cout << cur << endl;
insert_into_trie(cur, i);
}
fclose(fi);
int largest(-1),
ms, mf;
for (int i(0); i < N; ++i) {
//cout << A[i] << " ";
int aux = find_in_trie(A[i]);
//cout << A[aux] << endl;
if (A[i] ^ A[aux] > largest) {
largest = A[i] ^ A[aux];
ms = aux;
mf = i;
}
}
ofstream fout("xormax.out");
fout << (A[ms] ^ A[mf]) << " " << MIN(ms, mf) + 2 << " " << MAX(ms, mf) + 1 << endl;
fout.close();
return 0;
}