Cod sursa(job #773135)

Utilizator SteveStefan Eniceicu Steve Data 1 august 2012 05:17:17
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

int m1[50005];
int m2[50005];
int x[50005];

int main () {
	ifstream fin ("semne.in");
	int N, a, j = -1, k = -1;
	long long S, Sp = 0, Slol = 0;
	int v[50005];
	fin >> N >> S;
	for (int i = 0; i < N; i++)
	{
		fin >> v[i];
		Sp += 1LL * v[i];
	}
	Sp = (Sp - S) >> 1;
	
	srand (time (0));
	
	for (int i = 0; i < (N >> 1); i++)
		m1[++j] = i, Slol += v[i];
	for (int i = (N >> 1); i < N; i++)
		m2[++k] = i;
	
	while (Slol != Sp)
	{
		if (Slol < Sp)
		{
			a = rand () % k;
			Slol += v[m2[a]];
			m1[++j] = m2[a];
			m2[a] = m2[k--];
		}
		if (Slol > Sp)
		{
			a = rand () % j;
			Slol -= v[m1[a]];
			m2[++k] = m1[a];
			m1[a] = m1[j--];
		}
	}
	for (int i = 0; i <= j; i++)
	{
		x[m1[i]] = 1;
	}
	ofstream fout ("semne.out");
	for (int i = 0; i < N; i++)
	{
		fout << (x[i] == 1 ? '-' : '+');
	}
	fin.close ();
	fout.close ();
	return 0;
}