Cod sursa(job #565500)

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

#define MAXN 50005

bitset<MAXN> semn;
vector<int> p, m;

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

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

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

    while (sum != s) {
        if (sum > s) {
            int i = rand () % p.size ();
            sum -= 2 * 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 * 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;
}