Cod sursa(job #1481827)

Utilizator tudorcomanTudor Coman tudorcoman Data 5 septembrie 2015 12:44:13
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int MAX_N = 50000;
int v[MAX_N], N, indPlus[MAX_N], p, indMinus[MAX_N], m, sCur, s;
char sol[MAX_N];

void solve() {

	if(sCur == s)
		return;

	int poz;
	if(sCur < s) {
		if(m == 0) return;
		poz = rand() % m;
		sCur += v[indMinus[poz]] << 1;
		indPlus[p ++] = indMinus[poz];
		indMinus[poz] = indMinus[-- m];
	} else {
		if(p == 0) return;
		poz = rand() % p;
		sCur -= v[indPlus[poz]] << 1;
		indMinus[m ++] = indPlus[poz];
		indPlus[poz] = indPlus[-- p];
	}

	solve();
}
int main() {

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

	srand(time(0));
	scanf("%d %d", &N, &s);

	for(register int i = 0; i < N; ++ i) {
		scanf("%d", &v[i]); 
		if(sCur < s) {
			indPlus[p ++] = i;
			sCur += v[i];
		} else {
			indMinus[m ++] = i;
			sCur -= v[i];
		}
	}

	solve();

	for(register int i = 0; i < p; ++ i)
		sol[indPlus[i]] = '+';

	for(register int i = 0; i < m; ++ i)
		sol[indMinus[i]] = '-';

	for(register int i = 0; i < N; ++ i)
		putc(sol[i], stdout);

	printf("\n");
	return 0;
}