Cod sursa(job #1666456)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 martie 2016 01:04:43
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 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, sum, s = 0, i, x;
   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 && cnta) {
         i = rand()%cnta;
         s -= 2*v[add[i]];
         swap(add[i], add[cnta-1]);
         sub[cnts++] = add[--cnta];
      }
      else if(cnts) {
         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;
}