Cod sursa(job #166693)

Utilizator pandaemonAndrei Popescu pandaemon Data 28 martie 2008 13:01:19
Problema Semne Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream.h>
#define NMAX 50003

long long n,S,i,suma;  int semn[NMAX];

long long limA,limB,where[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,int sign)
{
  i = rand()%lim_from+1; aux = from[ i ];

  semn[ aux.poz ]=sign; where[ aux.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);
    a[i].poz=i; suma+=a[i].val; semn[i]=1;}

  limA=n;

  while(suma!=S)
  {

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

  }


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


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