Cod sursa(job #1233246)

Utilizator Kira96Denis Mita Kira96 Data 25 septembrie 2014 00:17:24
Problema Semne Scor 5
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.85 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;
			++tp;
		}
		else
		{
			s-=x;
			M[++t]=mp(x,i);
			++t;
		}
	}
	while(s!=S)
	{
		if(s>S)
		{
			poz=rand()%tp;
			swap(P[poz],P[tp-1]);
			s-=P[--tp].fi*2;
			semn[P[tp].se]=0;
			M[++t]=P[tp];
		}
		else
		{
			poz=rand()%t;
			swap(M[poz],M[t-1]);
			s+=M[--t].fi*2;
			semn[M[t].se]=1;
			P[++tp]=M[t];
		}
	}
	FOR(i,1,n)
	if(semn[i])
		g<<"+";
	else
		g<<"-";
	return 0;
}