Cod sursa(job #2927346)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 20 octombrie 2022 10:03:13
Problema Semne Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 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]];

            for (int i = pos; i < Add.size()-1; ++ i )
                Add[i] = Add[i+1];
            Add.pop_back();
        }
        else {
            int pos = rnd() % Scad.size();

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

            for (int i = pos; i < Scad.size()-1; ++ i )
                Scad[i] = Scad[i+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;
}