Cod sursa(job #488664)

Utilizator SpiderManSimoiu Robert SpiderMan Data 29 septembrie 2010 17:14:49
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
# include <algorithm>
# include <bitset>
using namespace std ;

# define x first
# define y second

const char *FIN = "semne.in", *FOU = "semne.out" ;
const int MAX = 50005 ;

bitset < MAX > sol ;
pair < int, int > X[MAX] ;
int V[MAX] ;
int N, S ;
long long sum ;

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

    freopen ( FIN, "r", stdin ) ;
    scanf ( "%d %d", &N, &S ) ;
    for ( int i = 1; i <= N; ++i ) {
        scanf ( "%d", V + i ) ;
        if ( sum <= S ) {
            sum += V[i] ;
            X[++X[0].x].x = i ;
            sol[i] = 1 ;
        } else {
            sum -= V[i] ;
            X[++X[0].y].y = i ;
        }
    }

    while ( sum != S ) {
        if ( sum <= S ) {
            int a = rand () % X[0].y + 1 ;
            sum += V[ X[a].y ] << 1 ;
            sol[ X[a].y ] = 1 ;
            X[ ++X[0].x ].x = X[a].y ;
            X[a].y = X[ X[0].y --].y ;
        } else {
            int a = rand () % X[0].x + 1 ;
            sum -= V[ X[a].x ] << 1 ;
            sol[ X[a].x ] = 0 ;
            X[ ++X[0].y ].y = X[a].x ;
            X[a].x = X[ X[0].x --].x ;
        }
    }

    freopen ( FOU, "w", stdout ) ;
    for ( int i = 1; i <= N; ++i ) {
        printf ( "%c", sol[i] ? '+' : '-' ) ;
    }
}