Cod sursa(job #801551)

Utilizator toranagahVlad Badelita toranagah Data 24 octombrie 2012 18:05:37
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <cstdlib>
using namespace std;

ifstream fin("test.in");
ofstream fout("test.out");
const int MAX_N = 51000;

int sir[MAX_N];
int poz[MAX_N], neg[MAX_N];
char semn[MAX_N];
int N, S;
int sum;

void read_input();
void solve();
void write_output();

int main() 
{
	read_input();
	solve();
	write_output();
}

void read_input() {
	sum = 0;
	fin >> N >> S;
	for (int i = 1; i <= N; ++i) {
		fin >> sir[i];
		if (i < N / 2) {
			semn[sir[i]] = '-';
			neg[++neg[0]] = sir[i];
			sum -= sir[i];
		} else {
			semn[sir[i]] = '+';
			poz[++poz[0]] = sir[i];
			sum += sir[i];
		}
	}
}

void solve() {
	srand(time(0));
	while (sum != S) {
		if (sum < S) {
			int pos = rand() % neg[0] + 1;
			sum += 2 * neg[pos];
			semn[neg[pos]] = '+';
			poz[++poz[0]] = neg[pos];
			neg[pos] = neg[neg[0]];
			--neg[0];
		} else {
			int pos = rand() % poz[0] + 1;
			sum -= 2 * poz[pos];
			semn[poz[pos]] = '-';
			neg[++neg[0]] = poz[pos];
			poz[pos] = poz[poz[0]];
			--poz[0];
		}
	}
}

void write_output() {
	for (int i = 1; i <= N; ++i) {
		fout << semn[sir[i]];
	}
}