Pagini recente » Cod sursa (job #1178367) | Cod sursa (job #3233418) | Cod sursa (job #814818) | Cod sursa (job #3184725) | Cod sursa (job #2829313)
Utilizator |
chiar nu cont eaza |
Data |
8 ianuarie 2022 14:46:35 |
Problema |
Semne |
Scor |
95 |
Compilator |
cpp-64 |
Status |
done |
Runda |
lista2 |
Marime |
1.14 kb |
#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()%1000000000 <= 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]);
}