Cod sursa(job #3227956)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 4 mai 2024 12:51:12
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))

const long long max_size = 5e4 + 20;

long long v[max_size], sgn[max_size];
vector <long long> poz, neg;

void solve ()
{
    srand(time(NULL));
    long long n, s = 0, k;
    cin >> n >> k;
    for (long long i = 1; i <= n; i++)
    {
        cin >> v[i];
        s += v[i];
        poz.push_back(i);
    }
    while (s != k)
    {
        if (s > k)
        {
            long long pl = rand() % poz.size();
            swap(poz[pl], poz.back());
            pl = poz.back();
            poz.pop_back();
            s -= 2 * v[pl];
            neg.push_back(pl);
        }
        else
        {
            long long pl = rand() % neg.size();
            swap(neg[pl], neg.back());
            pl = neg.back();
            neg.pop_back();
            s += 2 * v[pl];
            poz.push_back(pl);
        }
    }
    for (auto f : poz)
    {
        sgn[f] = 1;
    }
    for (long long i = 1; i <= n; i++)
    {
        if (sgn[i] == 0)
        {
            cout << "-";
        }
        else
        {
            cout << "+";
        }
    }
}

signed main ()
{
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("semne.in", "r", stdin);
    freopen("semne.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long tt;
    //cin >> tt;
    tt = 1;
    while (tt--)
    {
        solve();
    }
    return 0;
}