Cod sursa(job #2239503)

Utilizator LucaSeriSeritan Luca LucaSeri Data 10 septembrie 2018 22:40:55
Problema Semne Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.01 kb
#include <bits/stdc++.h>
using namespace std;

typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > vll;
typedef vector< pii > vpii;
typedef long double ld;

ll lgput(ll a, ll b, ll mod) {
    ll ret = 1;
    while( b ){
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return ret;
}

int binarySearch(vector< int > &v, int value) {
    int best = 0;
    for(int step = 29; step >= 0; --step) {
        if(best + (1<<step) < v.size() && v[best + (1<<step)] <= value) best += (1<<step);
    }

    return best;
}

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

const int MAXN = 5e4 + 10;

bool semn[MAXN];
int v[MAXN];

vector< int > poz;
vector< int > neg;

int main() {
    ios::sync_with_stdio(false);

    long long n, s;
    f >> n >> s;

    long long currentSum = 0;
    for(int i = 1; i <= n; ++i) {
        f >> v[i];
        if(currentSum < s) {
            poz.emplace_back(i);
            semn[i] = true;
            currentSum += v[i];
        } else {
            neg.emplace_back(i);
            semn[i] = false;
            currentSum -= v[i];
        }
    }

    srand(time(NULL));

    while(currentSum != s) {
        if(currentSum < s) {
            assert(neg.size() != 0);
            int pos = rand() % neg.size();
            currentSum += 2 * v[neg[pos]];
            semn[neg[pos]] = true;
            swap(neg[pos], neg.back());
            poz.emplace_back(neg.back());
            neg.pop_back();
        } else {
            assert(poz.size() != 0);
            int pos = rand() % poz.size();
            currentSum -= 2* v[poz[pos]];
            semn[poz[pos]] = false;
            swap(poz[pos], poz.back());
            neg.emplace_back(poz.back());
            poz.pop_back();
        }
    }

    for(int i = 1; i <= n; ++i) {
        if(semn[i]) g << '+';
        else g << '-';
    }
    return 0;
}