Cod sursa(job #249515)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 28 ianuarie 2009 17:37:48
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <bitset>
#include <vector>

#define ppb pop_back
#define psb push_back

using namespace std;

const int maxN = 50010;
long long S, A;
int N, V[maxN];
bitset<maxN> Semn;
vector<int> pluss, minuss;

int main(){
    int i, x, now;

    freopen("semne.in", "r", stdin);
    freopen("semne.out", "w", stdout);

    for (i = 1, scanf("%d%lld", &N, &S), srand(time(NULL)); i <= N; ++i){
        scanf("%d", &V[i]);

        if (A + V[i] > S){
            minuss.psb(i);
            A -= V[i];
            Semn[i] = 0;
        }
        else{
            pluss.psb(i);
            A += V[i];
            Semn[i] = 1;
        }
    }

    while (A != S){
        if (A > S){
            x = rand() % pluss.size();
            now = pluss[x];
            A -= V[now] * 2;
            pluss[x] = pluss[pluss.size() - 1]; pluss.ppb();
            minuss.psb(now);
            Semn[now] = 0;
        }
        else{
            x = rand() % minuss.size();
            now = minuss[x];
            A += V[now] * 2;
            minuss[x] = minuss[minuss.size() - 1]; minuss.ppb();
            pluss.psb(now);
            Semn[now] = 1;
        }
    }

    for (i = 1; i <= N; ++i)
        printf("%c", (Semn[i] == 1) ? '+' : '-');
}