Cod sursa(job #2979230)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 14 februarie 2023 20:41:03
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

#define int long long

int a[50001];
bitset<50001>pls;

signed main()
{
    int n, k;
    in >> n >> k;

    vector<int>add, sub;

    int sum = 0;

    for (int i=1; i<=n; i++)
    {
        in >> a[i];
        sum += a[i];
        add.push_back(i);
    }

    while (sum != k)
    {
        if (sum > k)
        {
            if (add.empty())
            {
                return 0;
            }

            int pos = rand() % (add.size());
            sum -= 2 * a[add[pos]];
            sub.push_back(add[pos]);

            swap(add[pos], add[add.size()-1]);
            add.pop_back();
        }
        else
        {
            if (sub.empty())
            {
                return 0;
            }

            int pos = rand() % (sub.size());
            sum += 2 * a[sub[pos]];
            add.push_back(sub[pos]);

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

    for (int x : add)
        pls[x] =true;

    for (int i=1; i<=n; i++)
    {
        if (pls[i])
            out << '+';
        else
            out << '-';
    }

    return 0;
}