Cod sursa(job #193621)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 5 iunie 2008 15:28:56
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<stdlib.h>
#define N 50105
long long s,sum,a[N],n,min[N],pl[N],p,k;
char v[N];
int main(){
	int i,x;
	freopen("semne.in","r",stdin);
	freopen("semne.out","w",stdout);
	scanf("%lld %lld",&n,&s);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        if(sum+a[i]<=s)
			v[i]='+',sum+=a[i],pl[++p]=i;
        else
			sum-=a[i], v[i]='-',min[++k]=i;
        }
    while(sum!=s){
        if(sum<s){
            x=rand()%k+1;
            sum+=2*a[min[x]];
            pl[++p]=min[x];
            v[min[x]]='+';
            min[x]=min[k];
            k--;
            }
        else{
            x=rand()%p+1;
            sum-=2*a[pl[x]];
            min[++k]=pl[x];
            v[pl[x]]='-';
            pl[x]=pl[p];
            --p;
            }   
	}
    for(i=1;i<=n;++i)
		printf("%c",v[i]);
    return 0;
}