Cod sursa(job #2655233)

Utilizator alexradu04Radu Alexandru alexradu04 Data 3 octombrie 2020 17:43:26
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
int v[50010],sg[50010];
struct chestie{int val,poz;};
chestie p[50010],m[50010],aux;
int main(){
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    int n,i,x,nrp,nrm=0;
    long long s,sum=0;
    scanf("%d%lld",&n,&s);
    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
        p[i].val=v[i];
        p[i].poz=i;
        sum+=v[i];
    }
    nrp=n;
    srand(time(0));
    while(sum!=s)
        if(sum>s){
            x=rand()%nrp+1;
            nrm++;
            m[nrm]=p[x];
            sum-=2*p[x].val;
            swap(p[x],p[nrp]);
            nrp--;
        }
        else{
            x=rand()%nrm+1;
            nrp++;
            p[nrp]=m[x];
            sum+=2*m[x].val;
            swap(m[x],m[nrm]);
            nrm--;
        }
    for(i=1;i<=nrp;i++)
        sg[p[i].poz]=1;
    for(i=1;i<=n;i++)
        if(sg[i]==1)
            printf("+");
        else
            printf("-");
    return 0;
}