Cod sursa(job #977252)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 25 iulie 2013 11:51:34
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.18 kb
#include <fstream>
#include <ctime>
#include <algorithm>
using namespace std;
 
#define NMAX 50001
#define LL long long
 
LL i, N, S;
LL LM, LP, sum;
 
LL v[NMAX];
LL P[NMAX], M[NMAX];
 
LL x;
bool Conf[NMAX];
 
int main() {
    ifstream fin("semne.in");
    ofstream fout("semne.out");
    fin >> N >> S;
    srand(time(NULL));
    for (i = 0; i < N; ++i) {
        fin >> v[i];
        x = rand() % 2;
        Conf[i] = x;
        if (!x) {
            sum += (1LL * v[i]);
            P[LP++] = i;
        }
        else {
            sum -= (1LL * v[i]);
            M[LM++] = i;
        }
    }
    while (sum != S) {
        if (sum > S) {
            x = rand() % LP;
            sum -= (2 * v[P[x]]);
            M[LM++] = P[x];
            Conf[P[x]] = 1 - Conf[P[x]];
            swap(P[x], P[--LP]);
        }
        else {
            x = rand() % LM;
            sum += (2 * v[M[x]]);
            P[LP++]= M[x];
            Conf[M[x]] = 1 - Conf[M[x]];
            swap(M[x], M[--LM]);
        }
    }
    for (i = 0; i < N; ++i) {
        if (!Conf[i])
            fout << "+";
        else
            fout << "-";
    }
    return 0;
}