Cod sursa(job #1233240)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 25 septembrie 2014 00:07:12
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>

using namespace std;

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

vector <int> v,w;

int n,aux,x,y,i,j,m;

long long s,sum;

int main () {
    srand(time(0));
    fin>>n>>s;
    for (i=1;i<=n;i++) {
        fin>>x;
        if (sum<=s){
            sum+=x;
            v.push_back(x);
        }else {
            sum-=x;
            w.push_back(x);
        }
    }
    while (sum!=s) {
        if (sum>s) {
            x=v.size();
            y=rand()%x;
            aux=v[x-1];
            v[x-1]=v[y];
            v[y]=aux;
            w.push_back(v[x-1]);
            sum-=2*v[x-1];
            v.pop_back();
        }else {
            x=w.size();
            y=rand()%x;
            aux=w[x-1];
            w[x-1]=w[y];
            w[y]=aux;
            v.push_back(w[x-1]);
            sum+=2*w[x-1];
            w.pop_back();
        }
    }
    sort (v.begin(),v.end());
    sort (w.begin(),w.end());
    n=v.size();m=w.size();
    for (i=0,j=0; i<n && j<m;) {
        if (v[i]<=w[j]) {
            fout<<"+";
            i++;
        }else {
            fout<<"-";
            j++;
        }
    }
    for (;i<n;i++)
        fout<<"+";
    for(;j<m;j++)
        fout<<"-";

    return 0;
}