Cod sursa(job #1784052)

Utilizator TincaMateiTinca Matei TincaMatei Data 19 octombrie 2016 19:02:43
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <cstdlib>
#include <time.h>

const int MAX_N = 50000;
int plus[MAX_N], minus[MAX_N];
int v[MAX_N];
bool semn[MAX_N];

inline void swap(int *a, int *b) {
  int aux;
  aux = *a;
  *a = *b;
  *b = aux;
}

int main() {
  long long s, a, sa;
  int n, na, nb, x;
  FILE *fin = fopen("semne.in", "r");
  fscanf(fin, "%d%lld", &n, &s);
  a = 0LL;
  srand(time(NULL));
  for(int i = 0; i < n; ++i) {
    fscanf(fin, "%d", &v[i]);
    plus[i] = i;
    a = a + v[i];
  }

  sa = (a + s) / 2;
  fclose(fin);
  na = n;
  nb = 0;

  while(a != sa) {
    if(a > sa) {
      x = rand() % na;
      a = a - v[plus[x]];
      na--;
      swap(&plus[x], &plus[na]);
      swap(&plus[na], &minus[nb]);
      nb++;
    } else {
      x = rand() % nb;
      a = a + v[minus[x]];
      nb--;
      swap(&minus[x], &minus[nb]);
      swap(&minus[nb], &plus[na]);
      na++;
    }
  }

  for(int i = 0; i < na; i++) {
    semn[plus[i]] = true;
  }

  FILE *fout = fopen("semne.out", "w");
  for(int i = 0; i < n; i++)
    if(semn[i])
      fprintf(fout, "+");
    else
      fprintf(fout, "-");
  fclose(fout);
  return 0;
}