Cod sursa(job #761837)

Utilizator GrimpowRadu Andrei Grimpow Data 27 iunie 2012 16:25:35
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <ctime>
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define err pop_back

vector<int> pl,mn;

int n,v[500001];
long long S,ss;
string s;

void read ()
{
	ifstream in ("semne.in");
	in>>n>>S;
	for(int i=1;i<=n;++i)
		in>>v[i];
}

void solve ()
{
	ss=0;
	for(int i=1;i<=n;++i)
	{
		int k=rand()%2;
		if(k)
		{
			s+='+';
			pl.pb(i);
			ss+=v[i];
		}
		else
		{
			s+='-';
			mn.pb(i);
			ss-=v[i];
		}
	}
	for(;S-ss;)
		if(ss<S)
		{
			int k=rand()%mn.size();
			swap(mn[k],mn[mn.size()-1]);
			ss+=2*v[mn.back()];
			s[mn.back()-1]='+';
			pl.pb(mn.back());
			mn.err();
		}
		else
		{
			int k=rand()%pl.size();
			swap(pl[k],pl[pl.size()-1]);
			ss-=2*v[pl.back()];
			s[pl.back()-1]='-';
			mn.pb(pl.back());
			pl.err();
		}
}

void out ()
{
	ofstream out ("semne.out");
	out<<s;
}

int main ()
{
	srand(time(NULL));
	read ();
	solve ();
	out ();
	return 0;
}