Cod sursa(job #1081)

Utilizator varuvasiTofan Vasile varuvasi Data 12 decembrie 2006 16:50:14
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#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;
}