Pagini recente » Cod sursa (job #3198156) | Cod sursa (job #2335443) | Cod sursa (job #985408) | Cod sursa (job #216062) | Cod sursa (job #2418338)
#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();
}