Cod sursa(job #749105)

Utilizator matei_cChristescu Matei matei_c Data 15 mai 2012 19:39:46
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.3 kb
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;

const int MAX_N = 50001 ;

int n ;
int a[MAX_N] ;
int plus[MAX_N],minus[MAX_N] ;
char sol[MAX_N] ;
long long sum,suma ;

int main()
{
	
	srand( time(0) ) ;
	
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	
	int nrp = 0 ;
	int nrm = 0 ;
	scanf("%d%lld",&n,&suma);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		int x = rand() % 2 ;
		if(x == 1)
		{
            plus[++nrp] = i ;
            sum = (long long)(sum+a[i]) ;
            sol[i] = '+' ;
        }
		else
		{
            minus[++nrm] = i ;
            sum = (long long)(sum-a[i]) ;
            sol[i] = '-' ;
		}	
	}	
	
	while(sum != suma)
	{
        if (sum < suma)
		{
            int x = rand() % nrm + 1 ;
            plus[++nrp] = minus[x] ;
            minus[x] = minus[nrm] ;
            --nrm ;
            sum = (long long)(sum + 2 * a[plus[nrp]]) ;
            sol[plus[nrp]] = '+' ;
        }
		else
		{
            int x = rand() % nrp + 1 ;
            minus[++nrm] = plus[x] ;
            plus[x] = plus[nrp] ;
            --nrp ;
            sum = (long long)(sum - 2 * a[minus[nrm]]) ;
            sol[minus[nrm]] = '-' ;
        }
    }
	
	for(int i=1;i<=n;++i)
		printf("%c",sol[i]);
	printf("\n");
	
	return 0;
	
}