Cod sursa(job #61587)

Utilizator yoyolichIoana Ardeleanu yoyolich Data 19 mai 2007 23:09:21
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long v[50001];
long long p[50001];
long long m[50001];
long long semn[50001];
  

int main()
{
  freopen("semne.in","r",stdin);
  freopen("semne.out","w",stdout);

  long long n, a, b, i, s, tmp;

  scanf("%lld%lld", &n, &s);
  
  for(i=1;i<=n;++i)
   scanf("%lld",&v[i]);
  
  tmp= a= b= 0;

  for(i=1;i<=n;++i)
   {
    if(tmp+v[i]<=s)
     {
      p[++a]=i;
      tmp+=v[i];
      semn[i]=1;
     }
      else
     {
      m[++b]=i;
      tmp-=v[i];
      semn[i]=0;
     }
   }

  srand(time(0));
  long aux;

  while(tmp!=s)
   {
    if(tmp>s)
     {
      aux=(rand() % a)+1;
      semn[p[aux]]=0;
      m[++b]=p[aux];
      p[aux]=p[a--];
      tmp-=v[m[b]]<<1;
     }
      else
     {
      aux=(rand() % b)+1;
      semn[m[aux]]=1;
      p[++a]=m[aux];
      m[aux]=m[b--];
      tmp+=v[p[a]]<<1;
     }
   }

  for(i=1;i<=n;++i)
   if(semn[i])
    printf("+");
     else
    printf("-");

  return 0;
}