Cod sursa(job #785701)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 9 septembrie 2012 18:20:14
Problema Semne Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;

int v[50005];
bool semn[50005];
int minusuri[50005],plusuri[50005];

int main()
{
	int minus=0,plus=0;
	srand( time(NULL));
	long long s=0,sumatotala=0;
	int n;
	freopen("semne.in","r", stdin);
	freopen("semne.out","w",stdout);
	
	scanf("%d %d",&n,&s);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		if(i%2==0)
		{	
			semn[i]=0;// +
			sumatotala+=v[i];
			plusuri[++plus]=i;
		}
		else
		{
			semn[i]=1; // -
			sumatotala-=v[i];
			minusuri[++minus]=i;
		}
	}

	{
	while(sumatotala!=s)
		if(sumatotala<s)
		{
			int x=rand()%minus;
			if(minus==1)
				x=1;
			else
				while(x==0)
					x=rand()%minus;
			
			semn[minusuri[x]]=0;
			sumatotala+=2*v[minusuri[x]];
			plusuri[++plus]=minusuri[x];
			swap(minusuri[x],minusuri[minus]);
			--minus;
		}
		else
		{
			int x=rand()%plus;
			if(plus==1)
				x=1;
			else
				while(x==0)
					x=rand()%plus;
				
			semn[plusuri[x]]=1;
			sumatotala-=2*v[plusuri[x]];

			minusuri[++minus]=plusuri[x];
			swap(plusuri[x],plusuri[plus]);
			--plus;	
		}			
			
	}
	
	for(int i=1;i<=n;i++)
		if(semn[i]==0)
			printf("+");
		else
			printf("-");
	return 0;
}