Cod sursa(job #1950536)

Utilizator cristina_borzaCristina Borza cristina_borza Data 3 aprilie 2017 09:31:11
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.39 kb
#include <cstdlib>
#include <fstream>
#include <vector>
#include <ctime>

using namespace std;

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

const int Dim = 1e5;

vector <pair <long long, long long> > pls, mns;

long long n, x, S, sum;
char ans[ Dim ];

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

    f >> n >> S;
    for (int i = 1; i <= n; ++i) {
        f >> x;
        int sgn = rand () % 2;

        if (sgn == 1) {
            pls.push_back ({x, i});
            sum += x;
        }

        else {
            mns.push_back ({x, i});
            sum -= x;
        }
    }

    while (sum != S) {
        if (sum < S) {
            int pos = rand () % mns.size();
            sum += 2 * mns[pos].first;

            pls.push_back (mns[pos]);

            swap (mns[pos], mns[mns.size() - 1]);
            mns.pop_back();
        }

        else {
            int pos = rand () % pls.size();
            sum -= 2 * pls[pos].first;

            mns.push_back (pls[pos]);

            swap (pls[pos], pls[pls.size() - 1]);
            pls.pop_back();
        }
    }

    for (int i = 1; i <= n; ++i)
        ans[i] = '-';

    for (vector <pair <long long, long long> > :: iterator it = pls.begin(); it != pls.end(); ++it) {
        ans[it -> second] = '+';
    }

    for (int i = 1; i <= n; ++i) {
        g << ans[i];
    }
    return 0;
}