Pagini recente » Cod sursa (job #609158) | Cod sursa (job #1892105) | Cod sursa (job #362147) | Cod sursa (job #111199) | Cod sursa (job #2661435)
#include <iostream>
#include <fstream>
using namespace std;
ofstream g("xormax.out");
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
int n, nr;
struct date
{ int ans, pi, pf;
}sol, val;
struct Trie
{ int nrfii, cnt;
Trie *fiu[3];
Trie()
{ fiu[0] = fiu[1] = 0;
nrfii = cnt = 0;
}
};
Trie *T = new Trie;
void ins(Trie *nod, int x, int bit, int idx)
{ if(bit < 0)
{ nod->cnt = idx;
return;
}
nr = 0;
if(x & (1 << bit)) nr = 1;
if(!nod->fiu[nr])
{ nod->fiu[nr] = new Trie;
nod->nrfii++;
}
ins(nod->fiu[nr], x, bit-1, idx);
}
date query(Trie *nod, int x, int bit, int idx, int curr)
{ if(bit < 0)
{ date sol;
sol.ans = curr;
sol.pi = nod->cnt + 1;
sol.pf = idx;
return sol;
}
nr = 0;
if(x & (1 << bit)) nr = 1;
if(nod->fiu[1-nr])
{ curr = (curr << 1) + 1;
return query(nod->fiu[1-nr], x, bit-1, idx, curr);
}
else
{ curr = (curr << 1);
return query(nod->fiu[nr], x, bit-1, idx, curr);
}
}
int main()
{
InParser f("xormax.in");
f >> n;
int xr = 0;
sol.ans = -1;
ins(T, 0, 20, 0);
for(int i=1; i<=n; i++)
{ int x;
f >> x;
xr = xr ^ x;
ins(T, xr, 20, i);
val = query(T, xr, 20, i, 0);
if(val.ans > sol.ans) sol = val;
}
if(sol.pi > sol.pf) sol.pi = sol.pf;
g << sol.ans << ' ' << sol.pi << ' ' << sol.pf << '\n';
return 0;
}