Cod sursa(job #2798401)

Utilizator vladth11Vlad Haivas vladth11 Data 11 noiembrie 2021 11:42:29
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 50005;
const ll VMAX = 21;
const ll INF = (1LL << 55);
const ll MOD = 998244353;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 30;

ifstream fin("semne.in");
ofstream fout("semne.out");
ll semn[NMAX], n;
ll S;
ll v[NMAX], ini[NMAX], init[NMAX];
ll a[NMAX];

void bkt(ll k, ll s){
    if(s == S){
        for(ll i = 1; i <= n; i++){
            if(!semn[init[i]]){
                fout << "-";
            }else{
                fout << "+";
            }
        }
        exit(0);
    }
    if(s < S)
        return;
    if(k == n + 1)
        return;
    semn[k] = 0;
    bkt(k + 1, s - 2 * v[k]);
    semn[k] = 1;
    bkt(k + 1, s);
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    ll sum = 0;
    fin >> n >> S;
    for(ll i = 1; i <= n; i++){
        fin >> v[i];
        a[i] = v[i];
        ini[i] = i;
        sum += v[i];
        semn[i] = 1;
    }
    random_shuffle(ini + 1, ini + n + 1);
    for(ll i = 1;  i <= n; i++){
        init[ini[i]] = i;
        v[i] = a[ini[i]];
    }
    bkt(1, sum);
    return 0;
}