Cod sursa(job #1665514)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 27 martie 2016 00:14:50
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
    ifstream in("semne.in");
    ofstream out("semne.out");

    int n, s, cur_s;

    in >> n >> s;
    vector<pair<int,int>> add, sub;
    cur_s = 0;
    for(int i = 1, x; i <= n; i++) {
        in >> x;
        if(cur_s < s) {
            cur_s += x;
            add.push_back(make_pair(x, i-1));
        }
        else {
            cur_s -= x;
            sub.push_back(make_pair(x, i-1));
        }
    }
    srand(time(NULL));
    while(cur_s != s) {
        if(cur_s > s) {
            int pos = rand() % add.size();
            if(abs(s - cur_s + 2 * add[pos].first) < abs(s - cur_s)) {
                cur_s -= 2 * add[pos].first;
                swap(add[pos], add.back());
                sub.push_back(add.back());
                add.pop_back();
            }
        }
        else {
            int pos = rand() % sub.size();
            if(abs(s - cur_s - 2 * sub[pos].first) < abs(s - cur_s)) {
                cur_s += 2 * sub[pos].first;
                swap(sub[pos], sub.back());
                add.push_back(sub.back());
                sub.pop_back();
            }
        }
    }
    vector<char> sol(n, 0);
    for(const auto i : add) sol[i.second] = '+';
    for(const auto i : sub) sol[i.second] = '-';
    for(const auto i : sol) out << i;
    out << '\n';
    return 0;
}