Cod sursa(job #1233249)

Utilizator Kira96Denis Mita Kira96 Data 25 septembrie 2014 00:22:58
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.9 kb
#include<fstream>
#define N 51000
#include<vector>
#define pb push_back
#define FOR(a,b,c) for(int a=b;a<=c;++a)
#define mp make_pair
#define fi first
#define se second
using namespace std;
ifstream f("semne.in");
ofstream g("semne.out");
pair<int,int> P[N],M[N];
long long s,S;
int semn[N],x,n,tp,t,poz;
int main ()
{
	srand(time(0));
	f>>n>>S;
	FOR(i,1,n)
	{
		f>>x;
		if(s+x<=S)
		{
			s+=x;
			P[++tp]=mp(x,i);
			semn[i]=1;
		}
		else
		{
			s-=x;
			M[++t]=mp(x,i);
		}
	}
	while(s!=S)
	{
		if(s>S)
		{
			poz=rand()%tp+1;
			swap(P[poz],P[tp]);
			semn[P[tp].se]=0;
			M[++t]=P[tp];
			s-=P[tp--].fi*2;
		}
		else
		{
			poz=rand()%t+1;
			swap(M[poz],M[t]);
			semn[M[t].se]=1;
			P[++tp]=M[t];
			s+=M[t--].fi*2;
		}
	}
	FOR(i,1,n)
	if(semn[i])
		g<<"+";
	else
		g<<"-";
	return 0;
}
//Look at me! Look at me! The monster inside me has grown this big!