Cod sursa(job #3294714)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 27 aprilie 2025 15:44:49
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <fstream>
#include <vector>

using namespace std;
const int NMAX = 50001;
using ll = long long;

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

int v[NMAX];
bool semn[NMAX];

vector <int> neg, poz;
int main()
{
    srand(617823);
    int n;
    ll s, sum = 0;
    cin >> n >> s;
    for(int i = 1; i <= n; i++) {
        cin >> v[i];
        semn[i] = rand() % 2;
        if(!semn[i]) {
            neg.push_back(i);
            sum -= v[i];
        }
        else {
            poz.push_back(i);
            sum += v[i];
        }
    }
    //cout << sum << '\n';
    while(sum != s) {
        if(sum > s) { ///scadem un pozitiv
            int i = (rand()) % poz.size();

            neg.push_back(poz[i]);
            sum -= 2 * v[poz[i]];
            semn[poz[i]] = 0;

            swap(poz[i], poz.back());
            poz.pop_back();
        }
        else { ///adunam un negativ
            int i = (rand()) % neg.size();

            poz.push_back(neg[i]);
            sum += 2 * v[neg[i]];
            semn[neg[i]] = 1;

            swap(neg[i], neg.back());
            neg.pop_back();
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!semn[i])
            cout << "-";
        else
            cout << "+";
    }
    return 0;
}