Cod sursa(job #1585088)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 30 ianuarie 2016 19:08:18
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<fstream>
#include<ctime>
#include<cstdlib>
#include<vector>
#include<algorithm>

using namespace std;

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

typedef long long i64;

vector< i64 > p, m;

int main() {
    int n;
    i64 s, sum = 0;
    fin >> n >> s;
    for( int i = 0; i < n; ++ i ) {
        i64 x;
        fin >> x;
        p.push_back( x );
        sum += x;
    }

    srand( time( 0 ) );
    while ( sum != s ) {
        if ( sum > s ) {
            int ind = rand() % ( int )p.size();
            int aux = p[ ind ];
            p[ ind ] = p.back();
            p.back() = aux;

            m.push_back( p.back() );
            sum -= 2 * p.back();
            p.pop_back();
        } else {
            int ind = rand() % ( int )m.size();
            int aux = m[ ind ];
            m[ ind ] = m.back();
            m.back() = aux;

            p.push_back( m.back() );
            sum += 2 * m.back();
            m.pop_back();
        }
    }
    sort( p.begin(), p.end() );
    sort( m.begin(), m.end() );
    int i = 0, j = 0;
    while ( i < ( int )p.size() && j < ( int )m.size() ) {
        if ( p[ i ] < m[ j ] ) {
            fout << "+";
            ++ i;
        } else {
            fout << "-";
            ++ j;
        }
    }
    while ( i < ( int )p.size() ) {
        fout << "+";
        ++ i;
    }
    while ( j < ( int )m.size() ) {
        fout << "-";
        ++ j;
    }
    fin.close();
    fout.close();
    return 0;
}