Cod sursa(job #483002)

Utilizator darrenRares Buhai darren Data 6 septembrie 2010 14:38:06
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <ctime>
#include <cstdlib>
#include <fstream>

using namespace std;

long long n, s;
int v[50001];
int p1[50001], p2[50001];
bool h[50001];
long long sact;

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

	srand(time(0));

	fin >> n >> s;
	for (int i = 1; i <= n; ++i)
	{
		fin >> v[i];

		if (sact > s)
			sact -= v[i], p2[++p2[0]] = i, h[i] = true;
		else
			sact += v[i], p1[++p1[0]] = i;
	}

	while (sact != s)
		if (sact  > s)
		{
			int aux = rand() % p1[0] + 1;
			h[p1[aux]] = true;
			sact -= 2 * v[p1[aux]];

			p2[++p2[0]] = p1[aux];
			p1[aux] = p1[p1[0]--];
		}
		else
		{
			int aux = rand() % p2[0] + 1;
			h[p2[aux]] = false;
			sact += 2 * v[p2[aux]];

			p1[++p1[0]] = p2[aux];
			p2[aux] = p2[p2[0]--];
		}

	for (int i = 1; i <= n; ++i)
		fout << (h[i] == 0 ? '+' : '-');

	fin.close();
	fout.close();
}