Cod sursa(job #679174)

Utilizator titusuTitus C titusu Data 12 februarie 2012 20:40:30
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
using namespace std;
#include <cstdio>
#include <ctime>
#include <cstdlib>
int a[50005],v[50005],S,n,SS;

int plus[50005],minus[50005];

void inter(int &a,int &b){
	int aux = a; a=b; b=aux;
}

int main(){
	freopen("semne.in","r",stdin);
	scanf("%d%d",&n,&SS);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	
	for(int i = 1 ; i <= n ; ++i )
		if(rand() & 1)
			plus[++plus[0]] = i, S += a[i];
		else
			minus[++minus[0]] = i, S -= a[i];
	while(S-SS)
		if(S>SS){
			//iau din sirul de plus si adaug in minus
			int i = rand() % plus[0] +1;
			S -= 2*a[plus[i]];
			minus[++minus[0]] = plus[i];
			inter(plus[i],plus[plus[0]]);
			plus[0]--;
		}
		else{
			//iau din siurl de mius si il adug la plus
			int i = rand() % minus[0] +1;
			S += 2*a[minus[i]];
			plus[++plus[0]] = minus[i];
			inter(minus[i], minus[minus[0]]);
			--minus[0];
		}
	for(int i=1 ; i<=plus[0]; ++i)
		v[plus[i]] = 1;
	freopen("semne.out","w",stdout);
	for(int i=1;i<=n;++i)
		if(v[i])
			printf("+");
		else
			printf("-");
	printf("\n");
	return 0;
}