Cod sursa(job #1481825)

Utilizator tudorcomanTudor Coman tudorcoman Data 5 septembrie 2015 12:41:57
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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();

	fprintf(stderr, "%d %d %d\n", sCur, p, m);
	for(register int i = 0; i < p; ++ i)
		sol[indPlus[i]] = '+';

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

	puts(sol);
	return 0;
}