Cod sursa(job #383682)

Utilizator undogSavu Victor Gabriel undog Data 17 ianuarie 2010 17:41:13
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<cstdio>
#include<ctime>
#include<cstdlib>


long long v[50010],l[50010],r[50010];
char a[50010];


int main(){
	
	
	freopen("semne.in","r",stdin);
 	freopen("semne.out","w",stdout);
 	
 	long long Q,O;
 	long long n,S,nr,n1,n2;
	
	scanf("%lld%lld",&n,&S);

	srand(time (0));

	for(int i=0;i<n;++i){
    		scanf("%lld",&v[i]);
    		if(S>=Q){
        		a[i]=1;
        		l[n1]=i;
        		++n1;
	        	Q=Q+v[i];
    		}	
  	  	else if(S<Q){
	        	a[i]=2;
        		r[n2]=i;
        		++n2;
        		Q=Q-v[i];
    		}

	}

	while(Q!=S){
        	if(Q>S){
        		nr=rand()%n1;

        		a[l[nr]]=2;

        		Q=Q-v[l[nr]]-v[l[nr]];

        		r[n2]=l[nr];
        		++n2;
        		l[nr]=l[n1-1];
        		--n1;
        	}

        	else if(Q<S){
       		 	nr=rand()%n2;

        		a[r[nr]]=1;

        		Q=Q+v[r[nr]]+v[r[nr]];

        		l[n1]=r[nr];
       			++n1;
        		r[nr]=r[n2-1];
        		--n2;
        	}
	}
	for(int i=0;i<n;++i)
		if(a[i]==1)
			printf("+");
	else 
		printf("-");

	return 0;
}