Cod sursa(job #297653)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 5 aprilie 2009 15:20:01
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
long long s,sp;
long vp[50050],vn[50050],a[50050],x,i,n,poz,se[50050];
int main()
{
 srand(time(NULL));
 freopen("semne.in","r",stdin);
 freopen("semne.out","w",stdout);
 scanf("%lld%lld",&n,&s);
 for(i=1;i<=n;++i)
    {scanf("%lld",&a[i]);
     if(sp<s){vp[++vp[0]]=i;sp+=a[i];}
        else {vn[++vn[0]]=i;sp-=a[i];}}
 while(s!=sp)
   if(s>sp)
     {x=rand()%vn[0]+1;
      poz=vn[x];
      vn[x]=vn[vn[0]--];
      sp+=(2ll*a[poz]);
      vp[++vp[0]]=poz;}
        else
     {x=rand()%vp[0]+1;
      poz=vp[x];
      vp[x]=vp[vp[0]--];
      sp-=(2ll*a[poz]);
      vn[++vn[0]]=poz;}
 for(i=1;i<=vp[0];++i)se[vp[i]]=1;
 for(i=1;i<=n;++i)
    if(se[i])printf("+");
        else printf("-");
 printf("\n");
 return 0;
}