Cod sursa(job #2792401)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 1 noiembrie 2021 16:41:48
Problema Semne Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <vector>
#include <string>
#include <ctime>

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

std::vector <int> v;
std::vector <int> knapsack[2];
int sum[2], count[2];
// 0 - plus
// 1 - minus
std::string ans;

int get_rand (int sir) {
    return (rand() % count[sir]);
}

int main() {
    int n, s;
    fin >> n >> s;
    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        v.push_back(x);
    }
    for (int i = 0; i < n; i++) {
        if (sum[0] < sum[1] + s) {
            knapsack[0].push_back(i);
            sum[0] += v[i];
            count[0]++;
        } else {
            knapsack[1].push_back(i);
            sum[1] += v[i];
            count[1]++;
        }
    }
    srand(time(0));
    while (sum[0] != sum[1] + s) {
        if (sum[0] < sum[1] + s) {
            int aux = get_rand(1);
            knapsack[0].push_back(knapsack[1][aux]);
            sum[0] += v[knapsack[1][aux]];
            count[0]++;
            sum[1] -= v[knapsack[1][aux]];
            knapsack[1][aux] = knapsack[1][count[1] - 1];
            count[1]--;
            knapsack[1].pop_back();
        } else {
            int aux = get_rand(0);
            knapsack[1].push_back(knapsack[0][aux]);
            sum[1] += v[knapsack[0][aux]];
            count[1]++;
            sum[0] -= v[knapsack[0][aux]];
            knapsack[0][aux] = knapsack[0][count[0] - 1];
            count[0]--;
            knapsack[0].pop_back();
        }
    }
    ans.resize (n, '-');
    for (int i = 0; i < count[0]; i++)
        ans[knapsack[0][i]] = '+';
    fout << ans;
    return 0;
}