Cod sursa(job #291170)

Utilizator ProtomanAndrei Purice Protoman Data 29 martie 2009 14:35:30
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <time.h>

#define ll long long
#define pb push_back
#define MAX 50010

using namespace std;

vector <int> vctPoz, vctNeg;
int n;
ll s;
int semn[MAX], vctX[MAX]; 

int main()
{
	srand(time(NULL));
	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w", stdout);
	
	scanf("%d %lld", &n, &s);
	
	ll sp = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &vctX[i]);
		
		if (sp < s)
			vctPoz.pb(i), sp += vctX[i];
		else vctNeg.pb(i), sp -= vctX[i];
	}
	
	for (; sp != s; )
		if (sp < s)
		{
			int rd = rand() % vctNeg.size();
			int loc = vctNeg[rd];
			vctNeg[rd] = vctNeg[vctNeg.size() - 1];
			vctNeg.pop_back();
			sp += (ll) 2 * vctX[loc];
			vctPoz.pb(loc);
		}
		else
		{
			int rd = rand() % vctPoz.size();
			int loc = vctPoz[rd];
			vctPoz[rd] = vctPoz[vctPoz.size() - 1];
			vctPoz.pop_back();
			sp -= (ll) 2 * vctX[loc];
			vctNeg.pb(loc);
		}
	
	for (int i = 0; i < vctPoz.size(); i++)
		semn[vctPoz[i]] = 1;
	
	for (int i = 1; i <= n; i++)
		printf("%c", (semn[i])? '+' : '-');
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}