Cod sursa(job #726824)

Utilizator Catah15Catalin Haidau Catah15 Data 27 martie 2012 15:43:48
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>

using namespace std;

#define int64 long long
#define maxS 50010

int64 S, S2;
int A[maxS], M[maxS], P[maxS];
int dimM, dimP;
char sol[maxS];


int main()
{
	freopen ("semne.in", "r", stdin);
	freopen ("semne.out", "w", stdout);
	
	srand (time (0));
	
	int N;
	
	scanf ("%d %lld", &N, &S);
	
	for (int i = 0; i < N; ++ i)
	{
		scanf ("%d", &A[i]);
		
		int R = rand() % 2;
		
		if (R)
		{
			S2 -= A[i];
			sol[i] = '-';
			M[++ dimM] = i;
		}
		else
		{
			S2 += A[i];
			sol[i] = '+';
			P[++ dimP] = i;
		}
	}
	
	while (S2 != S)
	{
		if (S2 < S)
		{
			int poz = rand() % dimM + 1;
			swap (M[poz], M[dimM]);
			
			S2 += 2 * A[M[dimM]];
			sol[M[dimM]] = '+';
			
			P[++ dimP] = M[dimM];
			-- dimM;
		}
		else
		{
			int poz = rand() % dimP + 1;
			swap (P[poz], P[dimP]);
			
			S2 -= 2 * A[P[dimP]];
			sol[P[dimP]] = '-';
			
			M[++ dimM] = P[dimP];
			-- dimP;
		}
	}
	
	printf ("%s", sol);
	
	return 0;
}