Cod sursa(job #501331)

Utilizator ooctavTuchila Octavian ooctav Data 14 noiembrie 2010 19:08:14
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<iostream>
using namespace std;

const int NMAX = 50005;

int N, S;
int A[NMAX], p[NMAX], m[NMAX];
int sum = 0;

void citire()
{
	cin >> N >> S;
	for(int i = 1 ; i <= N ; i++)
	{
		cin >> A[i];
		if(sum < S)
			sum += p[++p[0]] = i;
		else
		{
			sum -= m[++m[0]] = i;
			A[i] = -A[i];
		}
	}
}

inline int modul(int x)
{
	if(x > 0) 
		return x;
	return -x;
}

void obtine()
{
	srand(time(0));
	while(sum != S)
	{
		if(sum < S)
		{
			int x = rand() % m[0] + 1;
			
			A[m[x]] *= -1;
			sum += 2 * A[m[x]];
			p[++p[0]] = m[x];
			
			m[x] = m[m[0]--];
		}
		else
		{
			int x = rand() % p[0] + 1;
			
			A[p[x]] *= -1;
			sum += 2 * A[p[x]];
			m[++m[0]] = p[x];
			
			p[x] = p[p[0]--];
		}
	}
}

void scrie()
{
	for(int i = 1 ; i <= N ; i++)
		if(A[i] > 0)
			printf("+");
		else
			printf("-");
}

int main()
{
	freopen("semne.in", "r", stdin);
	freopen("semne.out", "w", stdout);
	citire();
	obtine();
	scrie();
	return 0;
}