Cod sursa(job #1689539)

Utilizator robx12lnLinca Robert robx12ln Data 14 aprilie 2016 12:36:17
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#define DIM 50005
using namespace std;
FILE * fin = fopen("semne.in","r");
FILE * fout = fopen("semne.out","w");
int n, v[DIM], H1[DIM], H2[DIM], k1, k2;
char f[DIM];
long long sum, s;
int main(){
    fscanf( fin , "%d%lld", &n, &sum );
    s = 0;
    for( int i = 1; i <= n; i++ ){
        fscanf( fin , "%d%", &v[i] );
        if( s < sum ){
            s += v[i];
            H1[++k1] = i;
        }else{
            s -= v[i];
            H2[++k2] = i;
        }
    }
    srand( time( NULL ) );
    while( s != sum ){
        if( s > sum ){
            int p = rand() % k1 + 1;
            s -= 2 * v[ H1[p] ];
            swap( H1[p], H1[k1] );
            H2[++k2] = H1[k1];
            H1[k1] = 0;
            k1--;
        }else{
            int p = rand() % k2 + 1;
            s += 2 * v[ H2[p] ];
            swap( H2[p], H2[k2] );
            H1[++k1] = H2[k2];
            H2[k2] = 0;
            k2--;
        }
    }
    for( int i = 1; i <= k1; i++ ){
        f[ H1[i] ] = 1;;
    }
    for( int i = 1; i <= n; i++ ){
        if( f[i] == 1 ){
            fprintf( fout, "+" );
        }else{
            fprintf( fout, "-" );
        }
    }
    return 0;
}