Cod sursa(job #2792687)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 2 noiembrie 2021 10:28:58
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <string>
#include <cstdlib>
#include <ctime>

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

int const nmax = 50000;

int v[nmax + 5];
int knapsack[2][nmax + 5];
ll sum[2];
int count[2];
// 0 - plus
// 1 - minus
std::string ans;

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