Cod sursa(job #488661)
# 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, 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] ? '+' : '-' ) ;
}
}