Cod sursa(job #965549)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 24 iunie 2013 09:35:26
Problema Semne Scor 95
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.09 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>

using namespace std;

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

const int MAXN = 50005;

int v[MAXN] , pls[MAXN], mins[MAXN];
bitset<MAXN> semn;
long long sum, s;
int n, poz, nrp, nrm;

int main()
{
    srand(time(NULL));
    cin >> n >> s;
    for(int i = 1 ; i <= n ; ++ i)
    {
        cin >> v[i];
        pls[++nrp] = i;
        semn[i] = 1;
        sum += 1LL*v[i];
    }
    while( sum != s)
    {
       if(sum > s)
       {
           poz=rand()%nrp+1;
           sum-=2*v[pls[poz]];
           semn[pls[poz]]=0;
           mins[++nrm]=pls[poz];
           swap(pls[poz],pls[nrp]);
           nrp--;
      }
      else
      {
          poz=rand()%nrm+1;
          sum+=2*v[mins[poz]];
          semn[mins[poz]]=1;
          pls[++nrp]=mins[poz];
          swap(mins[poz],mins[nrm]);
          nrm--;
     }
    }
    for(int i = 1 ; i <= n ; ++ i)
        cout << ((semn[i]) ? "+" : "-");
    return 0;
}