Cod sursa(job #1051834)

Utilizator ELHoriaHoria Cretescu ELHoria Data 10 decembrie 2013 17:04:20
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <vector>

using namespace std;

int main()
{
	ifstream cin("semne.in");
	ofstream cout("semne.out");
	ios :: sync_with_stdio(false);
	const int nmax = 50002;
	int n;
	static int a[nmax];
	vector<int> withS[2];
	static bool sg[nmax];
	long long S;
	cin >> n >> S;
	srand(static_cast<unsigned int>(time(0)));
	long long sum = 0;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		if (sum < S) {
			sum += a[i];
			sg[i] = false;
		} else {
			sum -= a[i];
			sg[i] = true;
		} 
		withS[sg[i]].push_back(i);
	}

	int pos;
	while (sum != S) {
		if (sum < S) {
			pos = rand() % withS[1].size();
			sum += 2 * a[withS[1][pos]];
			sg[withS[1][pos]] = false;
			withS[0].push_back(withS[1][pos]);
			withS[1][pos] = withS[1].back();
			withS[1].pop_back();
		} else {
			pos = rand() % withS[0].size();
			sum -= 2 * a[withS[0][pos]];
			sg[withS[0][pos]] = true;
			withS[1].push_back(withS[0][pos]);
			withS[0][pos] = withS[0].back();
			withS[0].pop_back();
		}
	}
	for (int i = 0;i < n;i++) {
		cout << (sg[i] ? '-' : '+');
	}
	return 0;
}