Cod sursa(job #2691328)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 28 decembrie 2020 12:17:23
Problema Semne Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
 
const int DIM = 5e4 + 5;
 
int n, ans;
int a[DIM];
 
int main()
{
    freopen("semne.in", "r", stdin);
    freopen("semne.out", "w", stdout);
 
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
    scanf("%d%d", &n, &ans);
 
    int sum = 0;
 
    vector <int> p(n);
    vector <int> m;
    for (int i = 1; i <= n ; ++i) {
        scanf("%d", &a[i]);
        p[i - 1] = i;
        sum += a[i];
    }
 
    while (ans != sum) {
 
        if (ans < sum) {
            int pos = rng() % (int)p.size();
            sum = sum - 2 * a[p[pos]];
            m.push_back(p[pos]);
 
            swap(p[pos], p[(int)p.size() - 1]);
            p.pop_back();
        }
        else {
            int pos = rng() % (int)m.size();
            sum = sum + 2 * a[m[pos]];
            p.push_back(m[pos]);
 
            swap(m[pos], m[(int)m.size() - 1]);
            m.pop_back();
        }
    }
 
    string s;
    for (int i = 1; i <= n ; ++i) s.push_back('+');
 
    for (auto it : m) s[it - 1] = '-';
 
    cout << s;
 
    return 0;
}