Cod sursa(job #785252)

Utilizator visanrVisan Radu visanr Data 8 septembrie 2012 11:27:31
Problema Semne Scor 95
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.45 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
using namespace std;

#define pb push_back
#define ppb pop_back

int N, V[50010], semn[50010];
long long S, crtS;
vector<int> A, B;


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.pb(i);
          }else
          {
               crtS += V[i];
               semn[i] = 1;
               A.pb(i);
          }
    }
    while(crtS != S)
    {
               if(crtS > S)
               {
                       int pos = rand() % A.size();
                       crtS -= 2 * V[A[pos]];
                       B.pb(A[pos]);
                       semn[A[pos]] = -1;
                       A[pos] = A[A.size() - 1];
                       A.ppb();
               }else
               {
                    int pos = rand() % B.size();
                    crtS += 2 * V[B[pos]];
                    A.pb(B[pos]);
                    semn[B[pos]] = 1;
                    B[pos] = B[B.size() - 1];
                    B.ppb();
               }
    }
    for(i = 1; i <= N; i++)
          printf("%c", (semn[i] == 1 ? '+' : '-'));
    return 0;
}