Cod sursa(job #615084)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 8 octombrie 2011 15:54:56
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>

#define MAXN 50010
using namespace std;

int N, A[MAXN], gplus[MAXN], gmin[MAXN];
char r[MAXN];
int main() {

	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w", stdout);

	long long S, s = 0;
	scanf("%d %lld\n", &N, &S);
	
	
	for(int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
	}

	srand(time(NULL));
	
	int n, m;
	n = m = 0;
	for(int i = 1; i <= N; i++) {
		int bit = rand() % 2;
		if(bit != 0) {
			gplus[++n] = i;
			s += A[i];
		}
		else {
			gmin[++m] = i;
			s -= A[i];
		}
	}
	for(; ; ) {
		if(s == S) break;

		if(s < S) {
			int x1 = rand() % m; ++x1;
			gplus[++n] = gmin[x1];
			swap(gmin[x1], gmin[m]);
			--m;
			s += 2 * A[gplus[n]];
		}
		else if(s > S) {
			int x2 = rand() % n; ++x2;
			gmin[++m] = gplus[x2];
			swap(gplus[x2], gplus[n]);
			--n;
			s -= 2 * A[gmin[m]];
		}
	}
	for(int i = 1; i <= n; i++)
		r[gplus[i]] = '+';
	for(int i = 1; i <= m; i++)
		r[gmin[i]] = '-';
	for(int i = 1; i <= N; i++)
		printf("%c", r[i]);
	return 0;
}