Cod sursa(job #820298)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 20 noiembrie 2012 18:06:46
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.5 kb

#include <cstdio>
#include <ctime>
#include <cstdlib>

const int MAX_SIZE(50000);

int numbers [MAX_SIZE];
int minus [MAX_SIZE], minus_index;
int plus [MAX_SIZE], plus_index;
char sign [MAX_SIZE + 1];

int n;
long long sum, s;

inline void read (void)
{
	std::freopen("semne.in","r",stdin);
	std::scanf("%d%lld",&n,&s);
	for (int index(0) ; index < n ; ++index)
	{
		std::scanf("%d",&numbers[index]);
		if (std::rand() & 0x01)
		{
			sign[index] = '+';
			plus[plus_index] = index;
			++plus_index;
			sum += numbers[index];
		}
		else
		{
			sign[index] = '-';
			minus[minus_index] = index;
			++minus_index;
			sum -= numbers[index];
		}
	}
	--plus_index;
	--minus_index;
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("semne.out","w",stdout);
	std::printf("%s\n",sign);
	std::fclose(stdout);
}

inline void generate (void)
{
	int index;
	while (sum != s)
		if (sum > s)
		{
			if (plus_index)
				index = std::rand() % (plus_index + 1);
			else
				index = 0;
			sum -= numbers[plus[index]] << 1;
			sign[plus[index]] = '-';
			++minus_index;
			minus[minus_index] = plus[index];
			plus[index] = plus[plus_index];
			--plus_index;
		}
		else
		{
			if (minus_index)
				index = std::rand() % (minus_index + 1);
			else
				index = 0;
			sum += numbers[minus[index]] << 1;
			sign[minus[index]] = '+';
			++plus_index;
			plus[plus_index] = minus[index];
			minus[index] = minus[minus_index];
			--minus_index;
		}
}

int main (void)
{
	std::srand(std::time(0));
	read();
	generate();
	print();
	return 0;
}