Cod sursa(job #340481)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 14 august 2009 21:40:19
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int n,v[50005],v1[50005],v2[50005],sol[50005];
long long s,suma;
int main()
{
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	srand(time(0));
	scanf("%d%lld",&n,&s);
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		if(suma<s)
		{
			suma+=v[i];
			v1[++v1[0]]=i;
			sol[i]=1;
		}
		else
		{
			suma-=v[i];
			v2[++v2[0]]=i;
		}
	}
	while(s!=suma)
		if(suma<s)
		{
			i=rand()%v2[0]+1;
			suma+=(v2[i]<<1);
			sol[v2[i]]=1;
			v1[++v1[0]]=v2[i];
			v2[i]=v2[v2[0]];
			v2[0]--;
		}
		else
		{
			i=rand()%v1[0]+1;
			suma-=(v1[i]<<1);
			sol[v1[i]]=0;
			v2[++v2[0]]=v1[i];
			v1[i]=v1[v1[0]];
			v1[0]--;
		}
	for(i=1;i<=n;i++)
		if(sol[i])
			printf("+");
		else
			printf("-");
	return 0;
}