Cod sursa(job #1783101)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 18 octombrie 2016 19:35:05
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
# include <iostream>
# include <fstream>

# include <fstream>
# include <vector>
# include <cstdlib>

using namespace std;

# define MAX_N 50000

unsigned v[MAX_N];
char str[MAX_N];

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

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

    int n, i, nr, r;
    long long s;

    fin >> n >> s;

    for ( i = 0; i < n; i ++ )
        fin >> v[i];

    vector<unsigned> v1, v2;
    v1.reserve( n );
    v2.reserve( n );

    for ( i = 0; i < n; i ++ ) {
        if ( s >= 0 ) {
            v1.push_back( i );
            s -= v[i];
        } else {
            v2.push_back( i );
            s += v[i];
        }
    }

    while ( s != 0 ) {
        if ( s > 0 ) {
            r = rand() % v2.size();

            s -= 2 * v[v2[r]];

            v1.push_back( v2[r] );
            swap( v2[r], v2.back() );
            v2.pop_back();
        } else {
            r = rand() % v1.size();

            s += 2 * v[v1[r]];

            v2.push_back( v1[r] );
            swap( v1[r], v1.back() );
            v1.pop_back();
        }
    }


    for ( unsigned i : v1 )
        str[i] = '+';
    for ( unsigned i : v2 )
        str[i] = '-';

    fout << str << endl;

    fin.close();
    fout.close();

    return 0;
}