Pagini recente » Cod sursa (job #488283) | Cod sursa (job #2192551) | Cod sursa (job #2234299) | Cod sursa (job #3213269) | Cod sursa (job #1081)
Cod sursa(job #1081)
#include <stdio.h>
#define max 100005
int N;
int arb[(1<<23)], X[max];
int nrbiti;
int start = 0, stop = 0;
int nrB(int nr)
{
int n = 0;
for (; nr; nr/=2, n++);
return n;
}
void Insert(int nr)
{
int i = 1, nrb = nrbiti;
while (nrb >= 0)
{
if ((nr >> nrb) & 1) i = i * 2 + 1;
else i = i * 2;
arb[i] = 1;
nrb--;
}
}
int Cauta(int nr)
{
int nrb = nrbiti, i = 1, val = 0;
while (nrb >= 0)
{
if ((nr >> nrb) & 1)
if (arb[i*2]) i = i * 2;
else i = i * 2 + 1;
else if (!((nr >> nrb) & 1))
if (arb[i*2+1]) i = i * 2 + 1;
else i = i * 2;
if (i % 2 == 1) val += (1 << nrb);
nrb--;
}
return val;
}
int main()
{
int v = 0;
FILE *fin = fopen("xormax.in", "rt");
fscanf(fin, "%d", &N);
fscanf(fin, "%d", &v);
X[1] = v;
nrbiti = nrB(X[1]);
int maxim = v, start = 1, stop = N;
for (int i = 2; i <= N; i++)
{
fscanf(fin, "%d", &v);
X[i] = X[i-1] ^ v;
int n = nrB(X[i]);
if (n > nrbiti) nrbiti = n;
maxim ^= v;
}
fclose(fin);
nrbiti--;
int cnt = 0;
Insert(X[1]);
for (int i = 2; i <= N; i++)
{
int n = Cauta(X[i]);
if ((n ^ X[i]) > maxim)
{
maxim = n ^ X[i], cnt = 1; stop = i;
start = i;
while (X[start] != n && start > 1) start --;
start++;
}
else if ((n ^ X[i]) == maxim) cnt++;
Insert(X[i]);
}
FILE *fout = fopen("xormax.out", "wt");
fprintf(fout, "%d %d %d", maxim, start, stop);
fclose(fout);
return 0;
}