Cod sursa(job #785244)

Utilizator visanrVisan Radu visanr Data 8 septembrie 2012 11:23:34
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std;


int A[50010], B[50010], K1, K2, N, V[50010], semn[50010];
long long S, crtS;


int main()
{
    freopen("semne.in", "r", stdin);
    freopen("semne.out", "w", stdout);
    srand(time(0));
    int i;
    scanf("%i %lld", &N, &S);
    for(i = 1; i <= N; i++)
    {
          scanf("%i", &V[i]);
          if(crtS + V[i] > S)
          {
                  crtS -= V[i];
                  semn[i] = -1;
                  B[K2 ++] = i;
          }else
          {
               crtS += V[i];
               semn[i] = 1;
               A[K1 ++] = i;
          }
    }
    while(crtS != S)
    {
               if(crtS > S)
               {
                       int pos = rand() % K1;
                       crtS -= 2 * V[A[pos]];
                       B[K2 ++] = A[pos];
                       semn[A[pos]] = -1;
                       A[pos] = A[K1];
                       K1 --;
               }else
               {
                    int pos = rand() % K2;
                    crtS += 2 * V[B[pos]];
                    A[K1 ++] = B[pos];
                    semn[B[pos]] = 1;
                    B[pos] = B[K2];
                    K2 --;
               }
    }
    for(i = 1; i <= N; i++)
          printf("%c", (semn[i] == 1 ? '+' : '-'));
    return 0;
}