Cod sursa(job #83040)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 9 septembrie 2007 21:14:39
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>



 long long n, a, b, i, s, tmp, m[50000], p[50000], v[50000], semn[50000];


int main()
{
  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]);
  
  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;
}