Cod sursa(job #565482)

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

#define MAXN 50005

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

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

inline int move (int s, int t)
{
    int i = rand () % n;
    v[p[t][1]++][t] = v[i][s];
    p[s][0] -= v[i][s];
    p[t][0] += v[i][s];
    v[i][s] = v[p[s][1] - 1][s];
    v[p[s][1] - 1][s] = 0;
    p[s][1]--;

    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 (p[0][0] + x <= s) {
            v[p[0][1]++][0] = x;
            p[0][0] += x;
            semn[x] = true;
        } else {
            v[p[1][1]++][1] = x;
            p[1][0] += x;
            semn[x] = false;
        }
    }

    while ((p[0][0] - p[1][0]) != s) {
        while ((p[0][0] - p[1][0]) < s) {
            move (1, 0);
        }
        while ((p[1][0] - p[0][1]) < s) {
            move (0, 1);
        }
    }

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

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