Cod sursa(job #1533625)

Utilizator SilviuIIon Silviu SilviuI Data 22 noiembrie 2015 19:56:49
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define nmax 50010
using namespace std;
int n,i,j,t[nmax],fr[nmax],up[nmax],down[nmax],up1,down1;
long long int s=0,m;
int main() {
freopen("semne.in","r",stdin);
freopen("semne.out","w",stdout);
scanf("%d %lld",&n,&m); srand(unsigned(time(0)));
for (i=1;i<=n;i++) {
    scanf("%d",&t[i]);
    if (s+t[i]<=m) s+=t[i],fr[i]=1,up1++,up[up1]=i; else
        s-=t[i],fr[i]=-1,down1++,down[down1]=i;
}
while (s!=m) {
    if (s<m) {
        int x=0;
        while (x==0) x=rand()%(down1+1);
        s+=2*t[down[x]]; fr[down[x]]=1; up1++; up[up1]=down[x]; down[x]=down[down1]; down1--;
    } else
    if (s>m) {
        int x=0;
        while (x==0) x=rand()%(up1+1);
        s-=2*t[up[x]]; fr[up[x]]=-1; down1++; down[down1]=up[x]; up[x]=up[up1]; up1--;
    }
}
for (i=1;i<=n;i++)
    if (fr[i]==1) printf("+"); else printf("-");
return 0;
}