Cod sursa(job #565493)

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

#define MAXN 50005

bitset<MAXN> semn;
int v[2][MAXN], p[2], n, sum = 0;

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

void move (int s, int t)
{
    int i = rand () % (p[s] - 1);

    v[t][p[t]++] = v[s][i];

    sum += v[s][i] * (t == 1 ? -2 : 2);

    v[s][i] = v[s][p[s] - 1];
    v[s][p[s] - 1] = 0;
    p[s]--;
}

int main ()
{
    int s;
    fin >> n >> s;

    srand (0);
    for (int i = 0, x; i < n; ++i) {
        fin >> x;
        if (sum + x <= s) {
            v[0][p[0]++] = x;
            sum += x;
        } else {
            v[1][p[1]++] = x;
            sum -= x;
        }
    }

    while (sum != s) {
        if (sum < s) {
            move (1, 0);
        } else {
            move (0, 1);
        }
    }

    for (int i = 0; i < p[0]; ++i){
       semn[v[0][i]] = true;
    }

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

    fout << endl;

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