Pagini recente » Cod sursa (job #2106397) | Cod sursa (job #2788076) | Cod sursa (job #1295512) | Cod sursa (job #194480) | Cod sursa (job #2829294)
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define cin fin
#define cout fout
ifstream cin("semne.in");
ofstream cout("semne.out");
int n;
int v[50001];
int ind[50001];
int inv[50001];
int suff[50001];
char semn[50001];
int S;
void bkt(int poz, int sum = 0) {
if(poz >= n && sum == S) {
for(int i = 0; i < n; i++)
cout << semn[inv[i]];
cout << '\n';
exit(0);
}
if(sum < S || S < sum - 2 * suff[poz])
return;
if(rand()%29 <= 1) {
semn[poz] = '+';
bkt(poz + 1, sum);
semn[poz] = '-';
bkt(poz + 1, sum - v[poz] * 2);
}
else {
semn[poz] = '-';
bkt(poz + 1, sum - v[poz] * 2);
semn[poz] = '+';
bkt(poz + 1, sum);
}
return;
}
int rnd(int a) {
return rand() % a;
}
signed main() {
srand(time(0));
cin >> n >> S;
for(int i = 0; i < n; i++)
cin >> v[i], semn[i] = '+', ind[i] = i;
random_shuffle(ind,ind+n,rnd);
for(int i = 0; i <n; i++)
inv[i] = v[i];
for(int i = 0; i < n; i++)
v[i] = inv[ind[i]];
for(int i = 0; i < n; i++)
inv[ind[i]] = i;
for(int i = n - 1; i >= 0; i--)
suff[i] = v[i] + suff[i + 1];
bkt(0,suff[0]);
}