Cod sursa(job #459829)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 31 mai 2010 12:37:13
Problema Semne Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
using namespace std;
ifstream in("semne.in");
ofstream out("semne.out");
int n,S,s,i,val,v[50001];
int main ()
{
	int s_plus[50001],s_minus[50001];
	s_plus[0]=0;
	s_minus[0]=0;
	in>>n>>S;
	for(i=1;i<=n;i++)
	{
		in>>v[i];
		if(s<S)
		{
			s+=v[i];
			s_plus[++s_plus[0]]=i;
		}
		else
		{
			s-=v[i];
			s_minus[++s_minus[0]]=i;
		}
	}
	srand(time(0));
	while(s!=S)
	{
		if(s<S)
		{
			val = rand()%s_minus[0]+1;
			s+=2*v[s_minus[val]];
			s_plus[++s_plus[0]]=s_minus[val];
			s_minus[val]=s_minus[s_minus[0]];
			s_minus[0]--;
		}
		else
		{
			val = rand()%s_plus[0]+1;
			s-=2*v[s_plus[val]];
			s_minus[++s_minus[0]]=s_plus[val];
			s_plus[val]=s_plus[s_plus[0]];
			s_plus[0]--;
		}
	}
	char semn[50000];
	for(i=1;i<=s_plus[0];i++)
	{
		semn[s_plus[i]]='+';
	}
	for(i=1;i<=s_minus[0];i++)
	{
		semn[s_minus[i]]='-';
	}
	for(i=1;i<=n;i++)
		out<<semn[i];
}