Cod sursa(job #2542968)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 10 februarie 2020 19:04:23
Problema Semne Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <stdlib.h>
#include <time.h>

std::ifstream fin("semne.in");
std::ofstream fout("semne.out");

const int MAX_N = 50000;

long long a[5 + MAX_N];
int nrp, plus[5 + MAX_N];
int nrm, minus[5 + MAX_N];
char sign[5 + MAX_N];

int main() {
  
  srand(time(NULL));
  
  int n;
  long long s, sum = 0;
  fin >> n >> s;
  for (int i = 1; i <= n; i++) {
    fin >> a[i];
    sign[i] = '+';
    plus[++nrp] = i;
    sum += a[i];
  }
  while (sum != s) {
    if (sum > s) {
      int pos = rand() % nrp;
      minus[++nrm] = plus[pos];
      sum -= 2 * a[plus[pos]];
      sign[plus[pos]] = '-';
      plus[pos] = plus[nrp--];
    } else {
      int pos = rand() % nrm;
      plus[++nrp] = minus[pos];
      sum += 2 * a[minus[pos]];
      sign[minus[pos]] = '+';
      minus[pos] = minus[nrm--];
    }
  }
  fout << sign + 1 << '\n';
  
  fin.close();
  fout.close();
  
  return 0;  
}