Cod sursa(job #1233195)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 24 septembrie 2014 22:10:01
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define infile "semne.in"
#define outfile "semne.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

vector<int> Plus, Minus;

long long S, s;

int nr, n;

int main() {
	f >> n >> S;
	for (int i = 1; i <= n; ++i) {
		f >> nr;
		if (s + nr <= S) {
			Plus.push_back(nr);
			s += nr;
		}
		else {
			Minus.push_back(nr);
			s -= nr;
		}
	}
	srand(time(NULL));
	while (S != s) {
		if (s > S) {
			int poz = rand() % Plus.size();
			s -= (Plus[poz] << 1);
			int tmp = Plus[poz];
			Plus[poz] = Plus[Plus.size() - 1];
			Plus[Plus.size() - 1] = tmp;
			Plus.pop_back();
			Minus.push_back(tmp);
		}
		else {
			int poz = rand() % Minus.size();
			s += (Minus[poz] << 1);
			int tmp = Minus[poz];
			Minus[poz] = Minus[Minus.size() - 1];
			Minus[Minus.size() - 1] = tmp;
			Minus.pop_back();
			Plus.push_back(tmp);
		}
	}
	sort(Plus.begin(), Plus.end());
	sort(Minus.begin(), Minus.end());
	int i = 0, j = 0;
	while (i < Plus.size() && j < Minus.size())
	if (Plus[i] < Minus[j]) {
		g << "+";
		++i;
	}
	else {
		g << "-";
		++j;
	}
	for (; i < Plus.size(); ++i)
		g << "+";
	for (; j < Minus.size(); ++j)
		g << "-";
	return 0;
}

//This room. This bullet. There's a bullet for everyone. And a time. And a place. Yes... maybe this is how it has to be. - 47