Pagini recente » Cod sursa (job #1636359) | Cod sursa (job #2065858) | Cod sursa (job #132452) | Cod sursa (job #3040070) | Cod sursa (job #249515)
Cod sursa(job #249515)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <bitset>
#include <vector>
#define ppb pop_back
#define psb push_back
using namespace std;
const int maxN = 50010;
long long S, A;
int N, V[maxN];
bitset<maxN> Semn;
vector<int> pluss, minuss;
int main(){
int i, x, now;
freopen("semne.in", "r", stdin);
freopen("semne.out", "w", stdout);
for (i = 1, scanf("%d%lld", &N, &S), srand(time(NULL)); i <= N; ++i){
scanf("%d", &V[i]);
if (A + V[i] > S){
minuss.psb(i);
A -= V[i];
Semn[i] = 0;
}
else{
pluss.psb(i);
A += V[i];
Semn[i] = 1;
}
}
while (A != S){
if (A > S){
x = rand() % pluss.size();
now = pluss[x];
A -= V[now] * 2;
pluss[x] = pluss[pluss.size() - 1]; pluss.ppb();
minuss.psb(now);
Semn[now] = 0;
}
else{
x = rand() % minuss.size();
now = minuss[x];
A += V[now] * 2;
minuss[x] = minuss[minuss.size() - 1]; minuss.ppb();
pluss.psb(now);
Semn[now] = 1;
}
}
for (i = 1; i <= N; ++i)
printf("%c", (Semn[i] == 1) ? '+' : '-');
}