Cod sursa(job #624915)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 23 octombrie 2011 13:00:10
Problema Semne Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.31 kb
#include <iostream>
#include <cstdlib>
#include <vector>

#define NMax 50005

using namespace std;

vector <int> Plus, Minus;
int N;
long long V[NMax], S, Sum;
char Sign[NMax];

int main()
{
    freopen ("semne.in", "r", stdin);
    freopen ("semne.out", "w", stdout);
    srand (time (0));
    scanf ("%d %lld", &N, &S);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%lld", &V[i]);
        if (Sum<S)
        {
            Sign[i]='+';
            Sum+=V[i];
            Plus.push_back (i);
        }
        else
        {
            Sign[i]='-';
            Sum-=V[i];
            Minus.push_back (i);
        }
    }
    while (Sum!=S)
    {
        if (Sum>S)
        {
            int P=rand ()%Plus.size ();
            Sum-=(2*V[Plus[P]]);
            Minus.push_back (Plus[P]);
            Sign[Plus[P]]='-';
            Plus[P]=Plus[Plus.size ()-1];
            Plus.pop_back ();
        }
        else
        {
            int P=rand ()%Minus.size ();
            Sum+=(2*V[Minus[P]]);
            Plus.push_back (Minus[P]);
            Sign[Minus[P]]='+';
            Minus[P]=Minus[Minus.size ()-1];
            Minus.pop_back ();
        }
    }
    for (int i=1; i<=N; ++i)
    {
        printf ("%c", Sign[i]);
    }
    printf ("\n");
    return 0;
}