Cod sursa(job #2798487)

Utilizator ElizaTElla Rose ElizaT Data 11 noiembrie 2021 12:52:20
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

int vp[50005],vm[50005];
int v[50005];
char ch[50005];

int main()
{
    ifstream fin("semne.in");
    ofstream fout("semne.out");
    long long n,s,s1 = 0,x,cntp = 0,cntm = 0;
    fin >> n >> s;
    for (int i = 0;i < n;i++) {
        fin >> v[i];
        vp[cntp++] = i;
        ch[i] = '+';
        s1 += v[i];
    }
    while (s1 != s) {
        if (s1 > s) {
            x = rand() % cntp;
            s1 -= 2 * v[vp[x]];
            ch[vp[x]] = '-';
            vm[cntm++] = vp[x];
            swap(vp[x], vp[cntp - 1]);
            cntp--;
        }
        else {
            x = rand() % cntm;
            s1 += 2 * v[vm[x]];
            ch[vm[x]] = '+';
            vp[cntp++] = vm[x];
            swap(vm[x], vm[cntm - 1]);
            cntm--;
        }
    }
    for (int i = 0;i < n;i++)
        fout << ch[i];
    return 0;
}