Cod sursa(job #398022)

Utilizator toniobFMI - Barbalau Antonio toniob Data 17 februarie 2010 20:56:02
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

const int NMax = 50010;

int Nr, P[NMax], N[NMax], v[NMax];
long long S, sc;
bool B[NMax];

int main()
{
	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w", stdout);
	
	scanf("%d %lld", &Nr, &S);
	
	for (int i = 1; i <= Nr; ++i) 
	{
		scanf("%d",&v[i]);
		if (sc<S)
		{
			sc+=v[i];
			P[++P[0]]=i;
			B[i]=1;
		} else
		{
			sc-=v[i];
			N[++N[0]]=i;
		}
	}
	
	srand(time(NULL));
	
	while (sc!=S) {
		if (sc<S) {
			int r=rand()%N[0]+1;
			B[N[r]]=1;
			sc+=2*v[N[r]];
			P[++P[0]]=N[r];
			N[r]=N[N[0]];
			--N[0];
		} 
		else {
			int r=rand()%P[0]+1 ;
			B[P[r]]=0;
			sc-=2*v[P[r]];
			N[++N[0]]=P[r];
			P[r]=P[P[0]];
			--P[0];
		}
	}
	
	for (int i = 1; i <= Nr; i++) { 
		if (B[i]) {
			printf("+");
		}			
		else {
			printf("-");
		}
	}
	
	return 0;
}