Cod sursa(job #2239261)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 10 septembrie 2018 13:12:23
Problema Semne Scor 90
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.38 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("semne.in");
ofstream g ("semne.out");

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL_DEFINE
    freopen (".in", "r", stdin);
#endif
    srand (time (NULL));
	int n, s;
	f >> n >> s;
    vi a (n), neg, poz;
    vector <char> sgn (n);
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        f >> a[i];
        sum += a[i];
        sgn[i] = '+';
        poz.pb (i);
    }
    for ( ; ; ) {
        if (sum == s) {
            for (int i = 0; i < n; ++i) g << sgn[i];
            break;
        } else if (sum < s) {
            int pos = rand () % neg.size();
            sum += 2 * a[neg[pos]];
            poz.pb (neg[pos]);
            sgn[neg[pos]] = '+';
            neg[pos] = neg.back();
            neg.pop_back();
        } else {
            int pos = rand () % poz.size();
            sum -= 2 * a[poz[pos]];
            neg.pb (poz[pos]);
            sgn[poz[pos]] = '-';
            poz[pos] = poz.back();
            poz.pop_back();
        }
    }

    f.close();
    g.close();
    return 0;
}