Cod sursa(job #785937)

Utilizator Victor10Oltean Victor Victor10 Data 10 septembrie 2012 10:40:09
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
#define DM 50005

int v [DM], stmin [DM], stplus [DM];
bool answ [DM];
char afis [] = {'-', '+'};

int main (){
	
	freopen ("semne.in", "r", stdin);
	freopen ("semne.out", "w", stdout);
	
	int n, i, pozc, vfmin = 0, vfplus = 0;
	long long S, Sc = 0;
	int danu;
	srand (time (NULL));
	
	scanf ("%d%lld", &n, &S);
	
	for (i = 0; i < n; ++ i) {
		scanf ("%d", &v [i]);
		danu = rand () % 2;
		if  (!danu) {
			Sc -= v [i];
			answ [i] = 0;
			++ vfmin;
			stmin [vfmin] = i;

		}
		else {
			Sc += v [i];
			answ [i] = 1;
			++ vfplus;
			stplus [vfplus] = i;
		}
	}
	
	while (Sc != S) {
		if (Sc > S) {
			pozc = rand () % vfplus + 1;
			Sc -= (2 * v [stplus [pozc]]);
			answ [stplus [pozc]] = 0;
			stmin [++ vfmin] = stplus [pozc];
			swap (stplus [pozc], stplus [vfplus]);
			-- vfplus;
		}
		else if (Sc < S) {
			pozc = rand () % vfmin + 1;
			Sc += (2 * v [stmin [pozc]]);
			answ [stmin [pozc]] = 1;
			stplus [++ vfplus] = stmin [pozc];
			swap (stmin [pozc], stmin [vfmin]);
			-- vfmin;
			
		}
	}
	
	for (i = 0; i < n; ++ i)
		printf ("%c", afis [answ [i]]);

	printf ("\n");
}