Cod sursa(job #565507)

Utilizator nandoLicker Nandor nando Data 27 martie 2011 20:43:29
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <cstdlib>
#include <vector>
using namespace std;

#define MAXN 50005

typedef long long int64;

int v[MAXN];
bitset<MAXN> semn;
vector<int> p, m;

fstream fin ("semne.in", ios::in);
fstream fout ("semne.out", ios::out);

typedef vector<int>::iterator iter;

int main ()
{
    int64 s, sum = 0, n;
    fin >> n >> s;

    srand (time (NULL));
    for (int i = 0, x; i < n; ++i) {
        fin >> v[i];
        if (sum + v[i] <= s) {
            p.push_back (i);
            sum += v[i];
            semn[i] = true;
        } else {
            m.push_back (i);
            sum -= v[i];
            semn[i] = false;
        }
    }

    while (sum != s) {
        if (sum > s) {
            int i = rand () % p.size ();
            sum -= 2 * v[p[i]];
            semn[p[i]] = false;
            m.push_back (p[i]);
            p[i] = p[p.size () - 1];
            p.pop_back ();
        } else {
            int i = rand () % m.size ();
            sum += 2 * v[m[i]];
            semn[m[i]] = true;
            p.push_back (m[i]);
            m[i] = m[m.size () - 1];
            m.pop_back ();
        }
    }

    for (int i = 1; i <= n; ++i) {
        fout << (semn[i] ? '+' : '-');
    }

    fout << endl;

    fin.close ();
    fout.close ();
    return 0;
}