Cod sursa(job #3294736)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 27 aprilie 2025 19:18:14
Problema Semne Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>
#define in  fin
#define out fout

using namespace std;

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

int rndom(int maxi){
    int nr = rand() % maxi;
    return nr;
}

int semn_rando(){
    int nr = rand() % 2;
    return (nr == 1? 1 : -1);
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n, s; in >> n >> s;
    int v[n];

    for(int i = 0; i < n; i++) in >> v[i];

    vector<int> plus, mins;

    int current = 0; // suma curenta
    for(int i = 0; i < n; i++){
        int semn = semn_rando();
        current += semn * v[i];
        if(semn > 0) plus.push_back(v[i]);
        else mins.push_back(v[i]);
    }

    // cout << "plus : ";
    // for(int & i : plus) cout << i << " ";
    // cout << '\n';
    // cout << "mins : ";
    // for(int & i : mins) cout << i << " ";
    // cout << '\n';

    while(current != s){
        // cout << "current = " << current << '\n';
        // if(-100 > current || current > 100) break; // whoops
        if(current > s){
            int p = rndom(plus.size());
            // cout << "Scad " << plus[p] << '\n';
            current -= 2 * plus[p];
            auto it = lower_bound(mins.begin(), mins.end(), plus[p]);
            mins.insert(it, plus[p]);
            plus.erase(plus.begin() + p);
        }else{
            int p = rndom(mins.size());
            // cout << "Addd " << mins[p] << '\n';
            current += 2 * mins[p];
            auto it = lower_bound(plus.begin(), plus.end(), mins[p]);
            plus.insert(it, mins[p]);
            mins.erase(mins.begin() + p);
        }
    }

    int i1 = 0;
    for(int i = 0; i < n; i++){
        if(i1 < plus.size() && v[i] == plus[i1]){ out << "+"; i1++; }
        else out << "-";
    }


    return 0;
}