Cod sursa(job #2927348)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 20 octombrie 2022 10:05:13
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("semne.in");
ofstream g ("semne.out");

typedef long long LL;
constexpr int NMAX = 50005;

LL S;
LL A[NMAX];
int N;

vector <int> Add, Scad;
LL Sum = 0;

mt19937 rnd(6363617);

char semn[NMAX];

int main () {
    f >> N >> S;

    for (int i = 1; i <= N; ++ i ) {
        f >> A[i];
        Sum += A[i];
        Add.push_back(i);
    }

    while (Sum != S) {
        if (Sum > S) {
            int pos = rnd() % Add.size();

            Scad.push_back(Add[pos]);
            Sum -= 2*A[Add[pos]];

            swap(Add[pos], Add[Add.size()-1]);
            Add.pop_back();
        }
        else {
            int pos = rnd() % Scad.size();

            Add.push_back(Scad[pos]);
            Sum += 2*A[Scad[pos]];

            swap(Scad[pos], Scad[Scad.size()-1]);
            Scad.pop_back();
        }
    }

    for (auto it : Add)
        semn[it] = '+';
    for (auto it : Scad)
        semn[it] = '-';

    for (int i = 1; i <= N; ++ i )
        g << semn[i];
    g << '\n';

    return 0;
}