Cod sursa(job #2418338)

Utilizator SemetgTemes George Semetg Data 4 mai 2019 17:09:24
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <random>
using namespace std;

const string FILE_NAME = "semne";
const int N_MAX { 50005 };

ifstream in { FILE_NAME + ".in" };
ofstream out { FILE_NAME + ".out" };

int64_t N, S;
int64_t sum;
vector<int64_t> a(N_MAX), positive, negative;
vector<char> sign(N_MAX);

void init() {
    srand(time(0));
    
    in >> N >> S;
    
    for (int i { 1 }; i <= N; ++i) {
        in >> a[i];
        
        if (sum < S) {
            sum += a[i];
            sign[i] = '+';
            positive.push_back(i);
        } else {
            sum -= a[i];
            sign[i] = '-';
            negative.push_back(i);
        }
    }
}

void solve() {
    while (sum != S)
        if (sum > S) {
            int i = rand() % positive.size(), k = positive[i];
            sum -= 2 * a[k];
            
            sign[k] = '-';
            negative.push_back(k);
            
            swap(positive[i], positive.back());
            positive.pop_back();
        } else {
            int i = rand() % negative.size(), k = negative[i];
            sum += 2 * a[k];
            
            sign[k] = '+';
            positive.push_back(k);
            
            swap(negative[i], negative.back());
            negative.pop_back();
        }
}

void print() {
    for (int i { 1 }; i <= N; ++i)
        out << sign[i];
}

int main() {
    init();
    solve();
    print();
}