Cod sursa(job #2111798)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 22 ianuarie 2018 18:18:40
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.02 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>

const int MAXN = 5e4;

int v[MAXN + 1], m[MAXN + 1], p[MAXN + 1];
char a[MAXN + 1];

int main() {
  int n, pos, kp, km;
  long long s, scr;
  srand(time(NULL));
  FILE *f = fopen("semne.in", "r");
  fscanf(f, "%d%lld", &n, &s);
  scr = kp = km = 0;
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%d", &v[i]);
    if (v[i] + scr <= s) {
      p[++kp] = i;
      a[i] = '+';
      scr += v[i];
    } else {
      m[++km] = i;
      a[i] = '-';
      scr -= v[i];
    }
  }
  fclose(f);
  while (scr != s) {
    if (scr < s) {
      pos = rand() % km + 1;
      a[m[pos]] = '+';
      scr += 2 * v[m[pos]];
      p[++kp] = m[pos];
      m[pos] = m[km--];
    } else {
      pos = rand() % kp + 1;
      a[p[pos]] = '-';
      scr -= 2 * v[p[pos]];
      m[++km] = p[pos];
      p[pos] = p[kp--];
    }
  }
  f = fopen("semne.out", "w");
  for (int i = 1; i <= n; ++i) {
    fputc(a[i], f);
  }
  fprintf(f, "\n");
  fclose(f);
  return 0;
}