Pagini recente » Cod sursa (job #299033) | Cod sursa (job #1959261) | Cod sursa (job #2485497) | Cod sursa (job #2822205) | Cod sursa (job #340336)
Cod sursa(job #340336)
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX_N 50010
int poz[MAX_N], neg[MAX_N];
int vp[MAX_N], vn[MAX_N], semn[MAX_N];
int v[MAX_N];
int n, s, sum, ok1, ok2;
void cit() {
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
scanf("%d %d", &n, &s);
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
if (sum < s) {
poz[++poz[0]] = v[i];
vp[poz[0]] = i;
semn[i] = 1;
sum += v[i];
}
else {
neg[++neg[0]] = v[i];
vn[neg[0]] = i;
sum -= v[i];
}
}
}
void go1() {
ok1 = 1; ok2 = 0;
}
void go2() {
ok1 = 0; ok2 = 1;
}
void solve() {
srand(time(0));
while (sum != s) {
if (poz[0] && neg[0]) {
if (sum < s)
go1();
else go2();
}
else {
if (poz[0])
go2();
else go1();
}
if (ok1) {
//iau din numerele negative
int k = rand() % neg[0] + 1;
sum += 2 * neg[k];
semn[vn[k]] = 1;
poz[++poz[0]] = neg[k];
vp[poz[0]] = vn[k];
if (k != neg[0]) {
neg[k] = neg[neg[0]];
vn[k] = vn[neg[0]];
}
neg[0]--;
}
if (ok2) {
//iau din numerele pozitive
int k = rand() % poz[0] + 1;
sum -= 2 * poz[k];
semn[vp[k]] = 0;
neg[++neg[0]] = poz[k];
vn[neg[0]] = vp[k];
if (k != poz[0]) {
poz[k] = poz[poz[0]];
vp[k] = vp[poz[0]];
}
poz[0]--;
}
}
}
void write() {
for (int i = 1; i <= n; i++)
if (semn[i]) printf("+");
else printf("-");
printf("\n");
}
int main() {
cit();
solve();
write();
return 0;
}