Cod sursa(job #3222418)

Utilizator NuSuntRomanIspir Alexandru NuSuntRoman Data 9 aprilie 2024 23:58:36
Problema Semne Scor 90
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.06 kb
#include <bits/stdc++.h>
#define int long long

const int NMAX = 5e4 + 5;

struct elem {
    int x, id;
};

int n, S, sgn[NMAX];
elem a[NMAX];

std :: mt19937 rng(1337);

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

signed main() {
    fin >> n >> S;

    for (int i = 1; i <= n; ++ i) {
        fin >> a[i].x;

        a[i].id = i;

        S += a[i].x;
        a[i].x *= 2;
    }

    while (1) {
        std :: shuffle(a + 1, a + n + 1, rng);

        int curr = S;

        for (int i = 1; i <= n; ++ i) {
            if (curr >= a[i].x) {
                curr -= a[i].x;
                sgn[a[i].id] = +1;
            }
            else {
                sgn[a[i].id] = -1;
            }
        }

        if (curr == 0) {
            for (int i = 1; i <= n; ++ i) {
                if (sgn[i] == +1) {
                    fout << "+";
                }
                else {
                    fout << "-";
                }
            }

            return 0;
        }
    }

    return 0;
}