Cod sursa(job #1337588)

Utilizator vladrochianVlad Rochian vladrochian Data 9 februarie 2015 11:21:43
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

const int kMaxN = 50005;

ifstream fin("semne.in");
ofstream fout("semne.out");

int N, a[kMaxN];
long long S, crt;
char s[kMaxN];
vector<int> v[2];

int main() {
	srand(time(0));
	fin >> N >> S;
	for (int i = 0; i < N; ++i) {
		fin >> a[i];
		if (crt < S) {
			v[1].push_back(i);
			s[i] = '+';
			crt += a[i];
		} else {
			v[0].push_back(i);
			s[i] = '-';
			crt -= a[i];
		}
	}
	while (crt != S) {
		bool semn = crt > S;
		int pos = (rand() + rand()) % (int)v[semn].size();
		swap(v[semn][pos], v[semn].back());
		pos = v[semn].back();
		v[semn].pop_back();
		v[!semn].push_back(pos);
		if (semn) {
			S -= a[pos] << 1;
			s[pos] = '-';
		} else {
			S += a[pos] << 1;
			s[pos] = '+';
		}
	}
	fout << s << "\n";
	return 0;
}