Cod sursa(job #1144280)

Utilizator raulstoinStoin Raul raulstoin Data 16 martie 2014 20:46:09
Problema Semne Scor 45
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.74 kb
#include<fstream>
#include<cstdlib>

#define NMAX 50005

using namespace std;

ifstream fin("semne.in");
ofstream fout("semne.out");

int n,v[NMAX],poz,Plus[NMAX],Minus[NMAX],p,m,Signs[NMAX];
long long sum,s;

int main()
{
	fin>>n>>sum;
	for(int i=1;i<=n;i++)
	{
		fin>>v[i];
		s+=v[i];
		Plus[p++]=i;
	}
	while(s!=sum)
	{
		if(s>sum)
		{
			poz=rand()%p;
			Minus[m++]=Plus[poz];
			s-=2*v[Plus[poz]];
			Plus[poz]=Plus[p-1];
			p--;
			continue;
		}
		poz=rand()%m;
		Plus[p++]=Minus[poz];
		s+=2*v[Minus[poz]];
		Minus[poz]=Minus[m-1];
		m--;
	}
	for(int i=0;i<p;i++)
		Signs[Plus[i]]=1;
	for(int i=0;i<m;i++)
		Signs[-Minus[i]]=-1;
	for(int i=1;i<=n;i++)
		fout<<((Signs[i]>0)?('+'):('-'));
	return 0;
}