Cod sursa(job #1218908)

Utilizator mariusn01Marius Nicoli mariusn01 Data 12 august 2014 20:59:55
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>

using namespace std;
ifstream fin("semne.in");
ofstream fout("semne.out");

vector<int> P, M;
int n, i, x, aux, p, j;
long long s, sum;

int main() {
    srand(time(0));
    fin>>n>>s;
    for (i=1;i<=n;i++) {
        fin>>x;
        if (sum+x <= s) {
            P.push_back(x);
            sum += x;
        } else {
            M.push_back(x);
            sum -= x;
        }
    }

    while (s!=sum) {
        if (sum > s) {
            p = rand()%P.size();
            sum -= 2*P[p];
            aux = P[p];
            P[p] = P[ P.size()-1 ];
            P[ P.size()-1 ] = aux;
            M.push_back(P[ P.size()-1 ]);
            P.pop_back();
        } else {
            p = rand()%M.size();
            sum += 2*M[p];
            aux = M[p];
            M[p] = M[ M.size()-1 ];
            M[ M.size()-1 ] = aux;
            P.push_back(M[ M.size()-1 ]);
            M.pop_back();
        }
    }

    sort(P.begin(), P.end());
    sort(M.begin(), M.end());

    i = 0;
    j = 0;
    while (i<P.size() && j < M.size())
        if (P[i] < M[j]) {
            fout<<"+";
            i++;
        } else {
            fout<<"-";
            j++;
        }
    for (;i<P.size();i++)
        fout<<"+";
    for (;j<M.size();j++)
        fout<<"-";
    return 0;
}