Cod sursa(job #1206373)

Utilizator tudorv96Tudor Varan tudorv96 Data 9 iulie 2014 19:21:20
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

ifstream fin ("semne.in");
ofstream fout ("semne.out");

long long sum, n, s;
vector <long long> v[2];

int main() {
    srand (time(0));
    fin >> n >> s;
    for (long long x, i = 0; i < n; ++i) {
        fin >> x;
        if (sum < s) {
            v[0].push_back(x);
            sum += x;
        }
        else {
            v[1].push_back(x);
            sum -= x;
        }
    }
    while (sum != s) {
        if (sum < s) {
            unsigned r = rand() % v[1].size();
            sum += 2 * v[1][r];
            swap (v[1][r], v[1].back());
            v[0].push_back (v[1].back());
            v[1].pop_back();
        }
        else {
            unsigned r = rand() % v[0].size();
            sum -= 2 * v[0][r];
            swap (v[0][r], v[0].back());
            v[1].push_back (v[0].back());
            v[0].pop_back();
        }
    }
    sort (v[0].begin(), v[0].end());
    sort (v[1].begin(), v[1].end());
    int k[2] = {0, 0};
    while (k[0] < v[0].size() && k[1] < v[1].size() && k[0] + k[1] < n) {
        if (v[0][k[0]] < v[1][k[1]]) {
            fout << '+';
            k[0]++;
        }
        else {
            fout << '-';
            k[1]++;
        }
    }
    while (k[0] < v[0].size()) {
        fout << '+';
        k[0]++;
    }
    while (k[1] < v[1].size()) {
        fout << '-';
        k[1]++;
    }
}