Cod sursa(job #1665519)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 27 martie 2016 00:21:01
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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<int> vec, add, sub;
    cur_s = 0;
    for(int i = 0, x; i < n; i++) {
        in >> x;
        vec.push_back(x);
        if(cur_s < s) {
            cur_s += x;
            add.push_back(i);
        }
        else {
            cur_s -= x;
            sub.push_back(i);
        }
    }
    srand(time(NULL));
    while(cur_s != s) {
        if(cur_s > s) {
            int pos = rand() % add.size();
            cur_s -= 2 * vec[add[pos]];
            swap(add[pos], add.back());
            sub.push_back(add.back());
            add.pop_back();
        }
        else {
            int pos = rand() % sub.size();
            cur_s += 2 * vec[sub[pos]];
            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] = '+';
    for(const auto i : sub) sol[i] = '-';
    for(const auto i : sol) out << i;
    out << '\n';
    return 0;
}