Cod sursa(job #204448)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 24 august 2008 10:19:24
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#include<stdlib.h>
#define N 50102
long long s,v[N],n,S[N],sum,min[N],pl[N],a,b;
int main(){
	long long x,i;
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	scanf("%lld%lld",&n,&s);
	for(i=1;i<=n;++i)
		scanf("%lld",&v[i]);
	for(i=1;i<=n;++i){
		if(sum+v[i]<=s){
			pl[++a]=i;
			sum+=v[i];
			S[i]=1;
		}
		else{
			min[++b]=i;
			sum-=v[i];
			S[i]=0;
		}
	}
	while(sum!=s){
		if(sum>s){
			x=(rand()%a)+1;
			sum-=(v[pl[x]]<<1);
			S[pl[x]]=0;
			min[++b]=pl[x];
			pl[x]=pl[a--];
		}
		else{
			x=(rand()%b)+1;
			sum+=(v[min[x]]<<1);
			pl[++a]=min[x];
			S[min[x]]=1;
			min[x]=min[b--];
		}
	}
	for(i=1;i<=n;++i)
		if(S[i]==1)
			printf("+");
		else
			printf("-");
	fclose(stdin);
	fclose(stdout);
	return 0;
}