Cod sursa(job #2802518)

Utilizator lucametehauDart Monkey lucametehau Data 18 noiembrie 2021 12:21:28
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;

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

int n;
long long s, sum;

int v[50005];
vector <pair <int, int>> poz, neg;
bool sgn[50005];

int main() {
    cin >> n >> s;
    srand(time(0));

    for(int i = 1; i <= n; i++) {
        cin >> v[i];
        poz.push_back({v[i], i});
        sum += v[i];
    }

    while(sum != s) {
        if(sum < s) {
            int p = rand() % (int)neg.size();
            sum += 2 * neg[p].first;
            sgn[neg[p].second] ^= 1;
            poz.push_back(neg[p]);
            swap(neg[p], neg.back());
            neg.pop_back();
        } else {
            int p = rand() % (int)poz.size();
            sum -= 2 * poz[p].first;
            sgn[poz[p].second] ^= 1;
            neg.push_back(poz[p]);
            swap(poz[p], poz.back());
            poz.pop_back();
        }
    }

    for(int i = 1; i <= n; i++)
        cout << (sgn[i] == 1 ? '-' : '+');
    return 0;
}