Cod sursa(job #166669)

Utilizator pandaemonAndrei Popescu pandaemon Data 28 martie 2008 12:14:45
Problema Semne Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define NMAX 50003

long long n,S,i,suma;

long long limA,limB,where[NMAX],initial[NMAX];

struct mm {long long poz,val;} a[NMAX],b[NMAX],aux,nothing;


long long mutare(mm to[],mm from[],long long &lim_to,long long &lim_from)
{
  i = rand()%lim_from+1; aux = from[ i ];

				 where[ from[i].poz ] = ++lim_to;


  from[ i ] = from[ lim_from ];  where[ from[i].poz ] = i;

  from[ lim_from-- ] = nothing;

  to[ lim_to ] = aux;

  return aux.val;
}


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

  scanf("%lld %lld",&n,&S); srand( time(0) );

  for(i=1;i<=n;i++)
  { scanf("%lld",&a[i].val); initial[i]=a[i].val;
    a[i].poz=i;              suma+=initial[i];}

  limA=n;

  while(suma!=S)
  {

    if(suma<S) suma+=( mutare(a,b,limA,limB)<<1 );
    else suma-=( mutare(b,a,limB,limA)<<1 );

  }

  for(i=1;i<=n;i++)
   if( a [ where[i] ].val == initial[i]) printf("+");
   else printf("-");


  printf("\n"); return 0; }