Cod sursa(job #233738)

Utilizator zbarniZajzon Barna zbarni Data 19 decembrie 2008 00:41:17
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define g 50001
long long p[g],m[g],v[g],jel[g];

int main()
 {
  freopen("semne.in","r",stdin);
  freopen("semne.out","w",stdout);
  long long n,seg,i;
  long long sum,x,y,val;
  scanf("%lld%lld", &n, &sum);
     
  for(i=1;i<=n;++i)   
   scanf("%lld",&v[i]);   

  seg=x=y=0;
  for (i=1;i<=n;i++)
   {
    if (seg+v[i]<sum)
     {
      p[++x]=v[i];
      jel[i]=1;
      seg+=v[i];
     }
    else
     {
      m[++y]=v[i];
      jel[i]=2;
      seg-=v[i];
     }
   }
  srand(time(0));
  while (seg!=sum)
   {
    if (seg<sum)
     {
      val=(rand()%y)+1;
      jel[m[val]]=1;
      p[++x]=m[val];
      m[val]=m[y--];
      seg+=v[p[x]]<<1;
     }
    else
     {
      val=(rand()%x)+1;
      jel[p[val]]=2;
      m[++y]=p[val];
      p[val]=p[x--];
      seg-=v[m[y]]<<1;
     }
   }
  for (i=1;i<=n;i++)
   {
    if (jel[i]==1)
      printf("+");
    else
      printf("-");
   }
  printf("\n");
  return 0;
 }