Cod sursa(job #1241109)

Utilizator xtreme77Patrick Sava xtreme77 Data 12 octombrie 2014 17:54:07
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.58 kb
#include <fstream>
#include <ctime>
#include <cstdlib>

const char IN  [ ] = "semne.in" ;
const char OUT [ ] = "semne.out" ;
const int MAX = 50014 ;

#define mp make_pair

using namespace std;

typedef pair < int , int > PQ  ;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

long long s , S ;
int pluss , minuss ;
bool sign [ MAX ] ;
PQ M [ MAX ] , P [ MAX ] ;

int main(              )
{
    srand ( time ( NULL ) ) ;
    int n ;
    fin >> n >> S ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        int x ;
        fin >> x ;
        if ( s + x <= S )
        {
            s = s + x ;
            sign [ i ] = 1 ;
            ++ pluss ;
            P [ pluss ] = mp ( x , i ) ;
        }
        else {
            s = s - x ;
            sign [ i ] = 0 ;
            ++ minuss ;
            M [ minuss ] = mp ( x , i ) ;
        }
    }
    while ( s != S )
    {
        if ( s > S )
        {
            int poz = rand ( ) % pluss + 1 ;
            swap ( P [ poz ] , P [ pluss ] ) ;
            sign [ P [ pluss ].second ] = 0 ;
            M [ ++ minuss ] = P [ pluss ] ;
            s = s - ( P [ pluss -- ].first << 1 ) ;
        }
        else {
            int poz = rand ( ) % minuss + 1 ;
            swap ( M [ minuss ] , M [ poz ] ) ;
            sign [ M [ minuss ].second ] = 1 ;
            P [ ++ pluss ] = M [ minuss ] ;
            s = s + ( M [ minuss -- ].first << 1 ) ;
        }
    }
    for ( int i = 1 ; i <= n ; ++ i )
        if ( sign [ i ] == 1 )
            fout << "+" ;
        else fout << "-" ;
    return 0;
}