Cod sursa(job #671587)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 31 ianuarie 2012 17:57:18
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.33 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>

const int N = 50005;

int n, a[N], plus[N], minus[N];

bool sgn[N];

long long s, sc;

void read() {
  scanf("%d%lld", &n, &s);

  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
}

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

void init() {
  for (int i = 1; i <= n; ++i)
    if (rand() & 1) {
      sc += (long long)a[i];
      plus[++plus[0]] = i;
    } else {
      sc -= (long long)a[i];
      minus[++minus[0]] = i;
    }
}

void solve() {
  int poz;

  while (sc != s) {
    if (sc < s) {
      poz = 1 + rand() % minus[0];
      sc += (long long)2 * a[minus[poz]];
      plus[++plus[0]] = minus[poz];
      swap(minus[poz], minus[minus[0]]);
      --minus[0];
    } else {
      poz = 1 + rand() % plus[0];
      sc -= (long long)2 * a[plus[poz]];
      minus[++minus[0]] = plus[poz];
      swap(plus[poz], plus[plus[0]]);
      --plus[0];
    }
  }
}

void afis() {
  for (int i = 1; i <= plus[0]; ++i)
    sgn[plus[i]] = 1;

  for (int i = 1; i <= n; ++i)
    if (sgn[i])
      printf("+");
    else
      printf("-");
}

int main () {
  srand(time(0));

  freopen("semne.in", "r", stdin);
  freopen("semne.out", "w", stdout);

  read();

  init();

  solve();

  afis();

  return 0;
}