Cod sursa(job #83096)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 9 septembrie 2007 23:04:41
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
/*
100 p
*/

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<stdlib.h>

long long s, v[50002], n, semn[50002], suma, minus[50000], plus[50002], a, b;

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

  scanf("%lld %lld", &n, &s);
  srand(time(0)); 
  long long i, x;

  for (i=1; i<=n; i++) scanf("%lld",&v[i]);

  for(i=1; i<=n; i++)
  {
    if (suma+v[i]<=s)
    {
      plus[++a]=i;
      suma+=v[i];
      semn[i]++;
     }
      else
     {
      minus[++b]=i;
      suma-=v[i];
      semn[i]--;
     }
   }
  		
  srand(time(0));   

  while (suma!=s)
    {
	if (suma>s)
	{ x=(rand()%a)+1;
	  suma-=(v[plus[x]]<<1);
	  semn[plus[x]]--;
	  minus[++b]=plus[x];
	  plus[x]=plus[a--];
	}
	else
	{ x=(rand()%b)+1;
	  suma+=(v[minus[x]]<<1);
	  plus[++a]=minus[x];
	  semn[minus[x]]++;
	  minus[x]=minus[b--];
	}
    }
  for (i=1; i<=n; i++)
    if (semn[i]) 
 	 printf("+");
    else printf("-");
    
  return 0;
}