Cod sursa(job #307771)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 24 aprilie 2009 22:40:27
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>

using namespace std;

#define Nmax 50010
#define ll long long

#define file_in "semne.in"
#define file_out "semne.out"

ll sum,s;
ll x[Nmax];
ll p[Nmax];
ll m[Nmax];
int n,xx,i,j;
char semn[Nmax];

int main()
{
	srand(time(0));
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);


	scanf("%d %lld", &n,&s);

	sum=0;
	for (i=1;i<=n;++i)
	{
		scanf("%d", &x[i]);

		if (sum<=s)
		{
			sum+=x[i];
			semn[i]='+';
			p[0]++;
			p[p[0]]=i;
		}
		else
		{
			sum-=x[i];
			semn[i]='-';
			m[0]++;
			m[m[0]]=i;
		}
	}


	while(sum!=s)
		if (sum>s)
		  {
			  xx=rand()%p[0]+1;
			  sum-=(ll)(x[p[xx]]<<1);
			  semn[p[xx]]='-';
			  m[0]++;
			  m[m[0]]=p[xx];
			  p[xx]=p[p[0]];
			  p[p[0]]=0;
			  p[0]--;
		  }
		  else
		  {
			  xx=rand()%m[0]+1;
			  sum+=(ll)(x[m[xx]]<<1);
			  semn[m[xx]]='+';
			  p[0]++;
			  p[p[0]]=m[xx];
			  m[xx]=m[m[0]];
			  m[m[0]]=0;
			  m[0]--;
		  }


	for (i=1;i<=n;++i)
         printf("%c", semn[i]);


	fclose(stdin);
	fclose(stdout);

	return 0;
}