Cod sursa(job #2446411)

Utilizator CharacterMeCharacter Me CharacterMe Data 8 august 2019 19:48:18
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;
int n, i, nrm, nrp; char sign[50001];
long long s, pres=0LL, val[50001], pls[50001], mns[50001];
int main()
{
    freopen("semne.in", "r", stdin);
    freopen("semne.out", "w", stdout);
    scanf("%d%lld", &n, &s);
    for(i=1; i<=n; ++i){
        scanf("%lld", &val[i]);
        sign[i]='+';
        pres+=val[i];
        pls[++nrp]=i;
    }
    while(pres!=s){
        if(pres>s){
            i=rand()%nrp+1;
            swap(pls[nrp], pls[i]);
            pres=pres-2*val[pls[nrp]];
            sign[pls[nrp]]='-';
            mns[++nrm]=pls[nrp];
            --nrp;
        }
        else{
            i=rand()%nrm+1;
            swap(mns[nrm], mns[i]);
            pres=pres+2*val[mns[nrm]];
            sign[mns[nrm]]='+';
            pls[++nrp]=mns[nrm];
            --nrm;
        }
    }
    for(i=1; i<=n; ++i) printf("%c", sign[i]);
    return 0;
}