Cod sursa(job #2829316)

Utilizator eazachiar nu cont eaza Data 8 ianuarie 2022 14:47:24
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda lista2 Marime 1.13 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()%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]);
}