Cod sursa(job #1281791)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 decembrie 2014 19:01:48
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.05 kb
#include <fstream>

#include <cstdlib>
#include <ctime>
using namespace std;

const int MAX_N = 50002;

int N, na, nb;
int v[MAX_N], m[MAX_N], a[MAX_N], b[MAX_N];
long long S;

int main() {
    srand(time(NULL));

    ifstream f("semne.in");
    ofstream g("semne.out");

    f >> N >> S;

    long long A = 0, B = 0;
    for(int i = 1; i <= N; ++i) {
        f >> v[i];

        A += v[i];
        a[++na] = i;
    }

    while(A - B != S) {
        if(A - B > S) {
            int p = 1 + rand() % na;

            swap(a[p], a[na]);

            p = a[na];

            A -= v[p];
            B += v[p];
            m[p] = 1;

            b[++nb] = p;
            --na;
        }
        else {
            int p = 1 + rand() % nb;

            swap(b[p], b[nb]);

            p = b[nb];

            A += v[p];
            B -= v[p];
            m[p] = 0;

            a[++na] = p;
            --nb;
        }
    }

    for(int i = 1; i <= N; ++i)
        if(m[i])
            g << "-";
        else g << "+";
    g << "\n";

    f.close();
    g.close();

    return 0;
}