Cod sursa(job #3294737)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 27 aprilie 2025 19:30:01
Problema Semne Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 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];
    int semn[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 smn = semn_rando();
        current += smn * v[i];
        if(smn > 0){
            plus.push_back(i);
            semn[i] = 1;
        }else{
            mins.push_back(i);
            semn[i] = 0;
        }
    }

    // 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';
        // cout << "plus : ";
        // for(int & i : plus) cout << i << " ";
        // cout << '\n';
        // cout << "mins : ";
        // for(int & i : mins) cout << i << " ";
        // cout << '\n';

        if(current > s){
            int p = rndom(plus.size());
            current -= 2 * v[ plus[p] ];
            // cout << "  -- > Scad " << v[plus[p]] << '\n';
            mins.push_back(plus[p]);
            semn[ plus[p] ] ^= 1;
            swap(plus[p], plus.back()); plus.pop_back();
        }else{
            int p = rndom(mins.size());
            current += 2 * v[ mins[p] ];
            // cout << "  -- > Addd " << v[mins[p]] << '\n';
            plus.push_back(mins[p]);
            semn[ mins[p] ] ^= 1;
            swap(mins[p], mins.back()); mins.pop_back();
        }
    }
    // cout << "plus : ";
    // for(int & i : plus) cout << i << " ";
    // cout << '\n';
    // cout << "mins : ";
    // for(int & i : mins) cout << i << " ";
    // cout << '\n';

    int i1 = 0;
    for(int i = 0; i < n; i++){
        if(semn[i] == 1) out << "+";
        else out << "-";
    }


    return 0;
}