Cod sursa(job #1542738)

Utilizator Athena99Anghel Anca Athena99 Data 5 decembrie 2015 16:56:30
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <vector>

using namespace std;

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

typedef long long i64;

const int nmax= 50000;

bool u[nmax+1];
int v[nmax+1];

vector <int> m, p;

int main(  ) {
    int n;
    i64 s, sum= 0;
    fin>>n>>s;
    for ( int i= 1; i<=n; ++i ) {
        fin>>v[i];
        if ( (i64)sum+v[i]<=s ) {
            p.push_back(i);
            sum= (i64)sum+v[i];
        } else {
            m.push_back(i);
            sum= (i64)sum-v[i];
        }
    }

    srand(time(0));
    while ( sum!=s ) {
        int ms= (int)m.size(), ps= (int)p.size();
        if ( sum<s ) {
            int aux= rand()%ms;
            sum= (i64)sum+v[m[aux]]*2;
            p.push_back(m[aux]);
            m[aux]= m.back(); m.pop_back();
        } else {
            int aux= rand()%ps;
            sum= (i64)sum-v[p[aux]]*2;
            m.push_back(p[aux]);
            p[aux]= p.back(); p.pop_back();
        }
    }

    for ( vector <int>::iterator it= p.begin(); it!=p.end(); ++it ) {
        u[*it]= 1;
    }
    for ( int i= 1; i<=n; ++i ) {
        if ( u[i]==0 ) {
            fout<<"-";
        } else {
            fout<<"+";
        }
    }
    fout<<"\n";

    return 0;
}