Cod sursa(job #785866)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 9 septembrie 2012 23:37:32
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.18 kb
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef long long int64;

const int N = 50005;

int n;
int a[N], plus[N], minus[N];
bool semn[N];
int64 s, sum;

void read() {
	assert(freopen("semne.in", "r", stdin) != NULL);
	assert(freopen("semne.out", "w", stdout) != NULL);
	
	assert(scanf("%d %lld", &n, &s) == 2);
	for (int i = 1; i <= n; ++i) {
		assert(scanf("%d", &a[i]) == 1);
		plus[++plus[0]] = i;
		sum += a[i];
		semn[i] = 1;
	}
}

void solve() {
	srand(time(NULL));
	
	while (sum != s) {
		if (sum > s) {
			int randPoz = rand() % plus[0] + 1;
			
			sum -= 2 * a[plus[randPoz]];
			
			semn[plus[randPoz]] = 0;
			minus[++minus[0]] = plus[randPoz];
			
			plus[randPoz] = plus[plus[0]];
			--plus[0];
		} else {
			int randPoz = rand() % minus[0] + 1;
			
			sum += 2 * a[minus[randPoz]];
			
			semn[minus[randPoz]] = 1;
			plus[++plus[0]] = minus[randPoz];
			
			minus[randPoz] = minus[minus[0]];
			--minus[0];
		}
	}
}

void write() {
	for (int i = 1; i <= n; ++i)
		if (semn[i])
			printf("+");
		else
			printf("-");
}

int main() {
	read();
	solve();
	write();
}