Cod sursa(job #1666460)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 martie 2016 01:07:29
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

ifstream in("semne.in");
ofstream out("semne.out");

const int N = 50050;
int add[N], sub[N], v[N], cnta, cnts;
char sol[N];

int main() {
   int n, i, x;
   int64_t sum, s = 0;
   in >> n >> sum;
   for (i = 1; i <= n; i++) {
      in >> v[i];
      if (s < sum) {
         add[cnta++] = i;
         s += v[i];
      }
      else {
         sub[cnts++] = i;
         s -= v[i];
      }
   }
   srand(time(NULL));
   while (s != sum) {
      if (s > sum) {
         i = rand()%cnta;
         s -= 2*v[add[i]];
         swap(add[i], add[cnta-1]);
         sub[cnts++] = add[--cnta];
      }
      else {
         i = rand()%cnts;
         s += 2*v[sub[i]];
         swap(sub[i], sub[cnts-1]);
         add[cnta++] = sub[--cnts];
      }
   }
   for (i = 0; i < cnta; i++) sol[add[i]] = '+';
   for (i = 1; i <= n; i++) {
      if (!sol[i]) sol[i] = '-';
      out << sol[i];
   }
   return 0;
}