Cod sursa(job #3328287)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 7 decembrie 2025 16:53:36
Problema Semne Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("semne.in");
ofstream fout("semne.out");
const bool MINUS = 0;
const bool PLUS  = 1;
int n, s, i, sum[2], fr[2], v[50002], ruc[2][50002];
char c[50002];

static inline void Add(bool semn, int idx) {
    ruc[semn][++fr[semn]] = idx;
    sum[semn] += v[idx];
}

static inline void Swap(bool semn) {
    bool semnOp = !semn;
    int idx = (rand() % fr[semnOp]) + 1;

    ruc[semn][++fr[semn]] = ruc[semnOp][idx];

    sum[semn  ] += v[ruc[semnOp][idx]];
    sum[semnOp] -= v[ruc[semnOp][idx]];

    ruc[semnOp][idx] = ruc[semnOp][fr[semnOp]--];
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> s;
    for(i = 1; i <= n; i++) fin >> v[i];
    for(i = 1; i <= n; i++) {
        if(sum[PLUS] <= sum[MINUS] + s) Add(PLUS , i);
        else                            Add(MINUS, i);
    }

    srand(time(0));
    while(sum[PLUS] != sum[MINUS] + s) {
        if(sum[PLUS] < sum[MINUS] + s) Swap(PLUS);
        else                           Swap(MINUS);
    }

    for(i = 0; i < n; i++) c[i] = '-';
    for(i = 1; i <= fr[PLUS]; i++) c[ruc[PLUS][i] - 1] = '+';
    fout << c;

    return 0;
}