Cod sursa(job #1417729)

Utilizator Toast97Calin Farcas Toast97 Data 10 aprilie 2015 21:26:37
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <cstdlib>
#include <time.h>

using namespace std;

ifstream f ("semne.in");
ofstream g ("semne.out");

struct numar
{
    int indice;
    long long valoare;
} pozit[50005], negat[50005];

char sol[50005];

int main()
{
    srand (time (0));

    long long n, s, curent = 0, poz, nminus = -1, nplus = -1, nr;

    f >> n >> s;

    for (int i = 0; i < n; i ++)
    {
        f >> nr;

        ++ nplus;

        pozit[nplus].valoare = nr;
        pozit[nplus].indice = i;
        sol[i] = '+';

        curent += nr;
    }

    while (curent != s)
    {
        if (curent > s)
        {
            poz = rand () % nplus;

            negat[++ nminus] = pozit[poz];
            curent -= 2 * pozit[poz].valoare;
            sol[pozit[poz].indice] = '-';

            pozit[poz] = pozit[nplus];
            -- nplus;
        }
        else
        {
            poz = rand () % nminus;

            pozit[++ nplus] = negat[poz];
            curent += 2 * negat[poz].valoare;
            sol[negat[poz].indice] = '+';

            negat[poz] = negat[nminus];
            -- nminus;
        }
    }

    g << sol;

    f.close ();
    g.close ();
    return 0;
}