Cod sursa(job #337422)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 3 august 2009 16:23:41
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.67 kb
#include <cstdio>   
#include <ctime>   
#include <cstdlib>   
  
using namespace std;   
  
#define Nmax 50010   
#define ll long long   
  
#define file_in "semne.in"   
#define file_out "semne.out"   
  
ll sum,s;   
ll x[Nmax];   
ll p[Nmax];   
ll m[Nmax];   
int n,xx,i,j;   
char semn[Nmax];   
  
int main()   
{   
    srand(time(0));   
       
    freopen(file_in,"r",stdin);   
    freopen(file_out,"w",stdout);   
  
  
    scanf("%d %lld", &n,&s);   
  
    sum=0;   
    for (i=1;i<=n;++i)   
    {   
        scanf("%d", &x[i]);   
  
        if (sum<=s)   
        {   
            sum+=x[i];   
            semn[i]='+';   
            p[0]++;   
            p[p[0]]=i;   
        }   
        else  
        {   
            sum-=x[i];   
            semn[i]='-';   
            m[0]++;   
            m[m[0]]=i;   
        }   
    }   
  
  
    while(sum!=s)   
        if (sum>s)   
          {   
              xx=rand()%p[0]+1;   
              sum-=(ll)(x[p[xx]]<<1);   
              semn[p[xx]]='-';   
              m[0]++;   
              m[m[0]]=p[xx];   
              p[xx]=p[p[0]];   
              p[p[0]]=0;   
              p[0]--;   
          }   
          else  
          {   
              xx=rand()%m[0]+1;   
              sum+=(ll)(x[m[xx]]<<1);   
              semn[m[xx]]='+';   
              p[0]++;   
              p[p[0]]=m[xx];   
              m[xx]=m[m[0]];   
              m[m[0]]=0;   
              m[0]--;   
          }   
  
  
    for (i=1;i<=n;++i)   
         printf("%c", semn[i]);   
  
  
    fclose(stdin);   
    fclose(stdout);   
  
    return 0;   
}