Pagini recente » Cod sursa (job #34019) | Cod sursa (job #2837133) | Cod sursa (job #503888) | Cod sursa (job #768732) | Cod sursa (job #1668741)
#include <stdio.h>
#include <string.h>
using namespace std;
int x[100001];
char* s;
int last = 0;
class trie
{
public:
trie *v[2];
int indice, nrfii;
trie()
{
indice = nrfii = 0;
v[0] = v[1] = NULL;
}
void ins(char *s, int pos)
{
if(*s == 2)
{
this -> indice = pos;
return;
}
else
{
if(this -> v[*s] == NULL)
{
this -> v[*s] = new trie;
this -> nrfii++;
}
}
this -> v[*s] -> ins(s + 1, pos);
}
int pref(char *s)
{
if(*s == 2 || !this -> nrfii)
return this -> indice;
else
{
if(*s == 0)
{
if(this -> v[1])
return this -> v[1] -> pref(s + 1);
else
return this -> v[0] -> pref(s + 1);
}
else
{
if(this -> v[0])
return this -> v[0] -> pref(s + 1);
else
return this -> v[1] -> pref(s + 1);
}
}
}
};
trie *nod = new trie;
char ans[22];
char* converter (int x) {
for (int i = 0; i <= 20; i++) {
ans[i] = 0;
}
ans[21] = 2;
for (int pos = 20; x; x >>= 1, pos--) {
ans[pos] = x & 1;
}
char* p;
p = ans;
return ans;
}
int main()
{
FILE *fin, *fout;
fin = fopen("xormax.in", "r");
fout = fopen("xormax.out", "w");
int n;
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; i++)
{
fscanf(fin, "%d", &x[i]);
x[i] = (x[i] ^ x[i - 1]);
}
int max = 0, st, dr;
for(int i = 1; i <= n; i++)
{
s = converter(x[i]);
int val = nod -> pref(s);
if((x[i] ^ x[val]) > max)
{
max = (x[i] ^ x[val]);
st = val + 1;
dr = i;
}
nod -> ins(s, i);
}
fprintf(fout, "%d %d %d", max, st, dr);
return 0;
}