Cod sursa(job #350025)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 22 septembrie 2009 13:34:57
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.15 kb
#define bulan maxim :)

#include <cstdio>
#include <cstdlib>
#include <ctime>

#define IN "semne.in"
#define OUT "semne.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<17
#define ll long long

int N;
int V[N_MAX];
int minus[N_MAX],plus[N_MAX];
char sol[N_MAX];
ll S,sum;

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%lld",&N,&S);
	FOR(i,1,N)
	{
		scanf("%d", &V[i]);
		if((ll) sum + V[i] <= S)
			sum += (ll) V[i],
			plus[ ++plus[0] ] = i,
			sol[i] = '+';
		else
			sum -= (ll) V[i],
			minus[ ++minus[0] ] = i,
			sol[i] = '-';
	}		
}

void solve()
{
	int x;
	srand(time(0));
	while((ll) sum != S)
	{
		if(sum < S)
		{
			x = (rand() % minus[0]) + 1;
			sum += (ll) V[ minus[x] ]<<1;
			plus[ ++plus[0] ] = minus[x];
			sol[ minus[x] ] = '+';
			minus[ x ] = minus[ minus[0]-- ];
		}
		else
		{
			x = (rand() % plus[0]) + 1;
			sum -= (ll) V[ plus[x] ]<<1;
			minus[ ++minus[0] ] = plus[x];
			sol[ plus[x] ] = '-';
			plus[x] = plus[ plus[0]-- ];
		}
	}	
	FOR(i,1,N)
		printf("%c",sol[i]);
	printf("\n");	
}

int main()
{
	scan();
	solve();
	return 0;
}