Pagini recente » Cod sursa (job #2113591) | Cod sursa (job #2621951) | Cod sursa (job #206823) | Cod sursa (job #2399145) | Cod sursa (job #1538738)
#include <cstdio>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#define DIM 52000
#define cost second
#define position first
using namespace std;
int Freq[DIM], N, K1, K2, X;
pair <int, int> Stack1[DIM], Stack2[DIM];
long long S, T;
void pushStack1 (pair <int, int> value) {
Stack1[K1++] = value;
return;
}
void pushStack2 (pair <int, int> value) {
Stack2[K2++] = value;
return;
}
void popStack1 (int pos) {
Stack1[pos] = Stack1[K1-1]; K1 --;
return;
}
void popStack2 (int pos) {
Stack2[pos] = Stack2[K2-1]; K2 --;
return;
}
void getSolution () {
while (S != T) {
if (S >= T) {
if (K1 == 0) return;
int pos = rand() % K1;
pair <int, int> value = Stack1[pos];
S -= value.cost * 2;
popStack1 (pos);
pushStack2(value);
} else {
if (K2 == 0) return;
int pos = rand() % K2;
pair <int, int> value = Stack2[pos];
S += value.cost * 2;
popStack2 (pos);
pushStack1(value);
}
}
return;
}
int main () {
freopen ("semne.in", "r", stdin );
freopen ("semne.out","w", stdout);
srand (time(0));
scanf ("%d %lld", &N, &T);
for (int i = 1; i <= N; i ++) {
scanf ("%d", &X);
if (S <= T) {
pushStack1 (make_pair(i, X));
S += X;
} else {
pushStack2 (make_pair(i, X));
S -= X;
}
}
getSolution ();
for (int i = 0; i < K1; i ++)
Freq[Stack1[i].position] = 1;
for (int i = 1; i <= N; i ++)
printf ("%c", (Freq[i] == 1) ? '+' : '-');
return 0;
}