Cod sursa(job #565489)

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

#define MAXN 50005

bitset<MAXN> semn;
int v[MAXN][2], 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];

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

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

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

    semn[v[i][s]] = 1 - t;
}

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

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

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

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

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