Cod sursa(job #401915)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 23 februarie 2010 10:39:10
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.42 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define FIN "semne.in"
#define FOUT "semne.out"
#define NMAX 50010
using namespace  std;

int a[NMAX],n,p[NMAX],ng[NMAX];
char sgn[NMAX];
long long sum,S;

int main()
{
 srand(time(NULL));   
 freopen(FIN,"r",stdin);
 freopen(FOUT,"w",stdout);
 scanf("%d %lld",&n,&S);
 
 for(int i=1;i<=n;i++)
  {
         scanf("%lld",&a[i]);
         if(sum<S)
          {
                 sum+=a[i];
                 p[++p[0]]=i;
                 sgn[i]=1;
                 }
         else
         {
             sum-=a[i];
             ng[++ng[0]]=i;
             }        
         }   
 while(sum!=S) 
  {
               if(sum<S)
                {int x=rand()%(ng[0])+1;
                  
                   sum+=2*a[ng[x]];
                   sgn[ng[x]]=1;
                   p[++p[0]]=ng[x];
                   ng[x]=ng[ng[0]];
                   ng[0]--;
                              }
                else
                 {int x=rand()%(p[0])+1;
                   sum-=2*a[p[x]];
                   sgn[p[x]]=0;
                   ng[++ng[0]]=p[x];
                   p[x]=p[p[0]];
                   p[0]--;           
                                                     
                        }}
  for(int i=1;i<=n;i++)                      
     if(sgn[i]) printf("+");
     else printf("-");                      
    return 0;
    }