Pagini recente » Istoria paginii summer-challenge-2019/solutii/picazo | Monitorul de evaluare | Cod sursa (job #1772617) | Cod sursa (job #1302389) | Cod sursa (job #615084)
Cod sursa(job #615084)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#define MAXN 50010
using namespace std;
int N, A[MAXN], gplus[MAXN], gmin[MAXN];
char r[MAXN];
int main() {
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
long long S, s = 0;
scanf("%d %lld\n", &N, &S);
for(int i = 1; i <= N; i++) {
scanf("%d", &A[i]);
}
srand(time(NULL));
int n, m;
n = m = 0;
for(int i = 1; i <= N; i++) {
int bit = rand() % 2;
if(bit != 0) {
gplus[++n] = i;
s += A[i];
}
else {
gmin[++m] = i;
s -= A[i];
}
}
for(; ; ) {
if(s == S) break;
if(s < S) {
int x1 = rand() % m; ++x1;
gplus[++n] = gmin[x1];
swap(gmin[x1], gmin[m]);
--m;
s += 2 * A[gplus[n]];
}
else if(s > S) {
int x2 = rand() % n; ++x2;
gmin[++m] = gplus[x2];
swap(gplus[x2], gplus[n]);
--n;
s -= 2 * A[gmin[m]];
}
}
for(int i = 1; i <= n; i++)
r[gplus[i]] = '+';
for(int i = 1; i <= m; i++)
r[gmin[i]] = '-';
for(int i = 1; i <= N; i++)
printf("%c", r[i]);
return 0;
}