Cod sursa(job #1144275)

Utilizator raulstoinStoin Raul raulstoin Data 16 martie 2014 20:41:48
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<cstdlib>
#include<algorithm>

#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;
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--;
	}
	sort(Plus,Plus+p);
	sort(Minus,Minus+m);
	for(int i=0,j=0;i<p || j<m;)
	{
		if(i==p)
		{
			fout<<'-';
			j++;
			continue;
		}
		if(j==m)
		{
			fout<<'+';
			i++;
			continue;
		}
		if(Plus[i]<Minus[j])
		{
			fout<<'+';
			i++;
			continue;
		}
		fout<<'-';
		j++;
	}
	return 0;
}