Cod sursa(job #723941)

Utilizator ChallengeMurtaza Alexandru Challenge Data 26 martie 2012 08:13:30
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

const char InFile[]="semne.in";
const char OutFile[]="semne.out";
const int MaxN=50111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,V[MaxN],neg[MaxN],poz[MaxN];
long long S,SC;
char sol[MaxN];

int main()
{
	srand((unsigned int)(time(NULL)));
	
	fin>>N>>S;
	for(register int i=1;i<=N;++i)
	{
		fin>>V[i];
		sol[i]='+';
		SC+=V[i];
		poz[++poz[0]]=i;
	}
	fin.close();
	
	while(S!=SC)
	{
		if(SC>S)
		{
			int p=1+(rand()%poz[0]);
			swap(poz[p],poz[poz[0]]);
			neg[++neg[0]]=poz[poz[0]];
			--poz[0];
			SC-=(V[neg[neg[0]]]<<1);
			sol[neg[neg[0]]]='-';
		}
		else
		{
			int p=1+(rand()%neg[0]);
			swap(neg[p],neg[neg[0]]);
			poz[++poz[0]]=neg[neg[0]];
			--neg[0];
			SC+=(V[poz[poz[0]]]<<1);
			sol[poz[poz[0]]]='+';
		}
	}
	
	fout<<(sol+1);
	fout.close();
	return 0;
}