Cod sursa(job #1147617)

Utilizator lianaliana tucar liana Data 19 martie 2014 23:18:47
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#include<ctime>
#include<cstdlib>
#define nmax 50005
int n, i, p, pozx, ne[3];
int smn[nmax], mult[3][nmax];
long long sum[3], x, v[nmax], s;

int main()
{
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    srand(time(0));
    scanf("%ld %lld",&n,&s);
    for (i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        p=((sum[0]-sum[1])>s);
        sum[p]+=x;
        smn[i]=p;
        mult[p][++ne[p]]=i; v[i]=x;
    }
    while ((sum[0]-sum[1])!=s)
    {
        p=1-((sum[0]-sum[1])>s);
        pozx=rand()%ne[p]+1;  x=v[mult[p][pozx]];
        smn[mult[p][pozx]]=1-smn[mult[p][pozx]];
        sum[1-p]+=x;
        mult[1-p][++ne[1-p]]=mult[p][pozx];
        sum[p]-=x;
        mult[p][pozx]=mult[p][ne[p]];   ne[p]--;
    }
    for (i=1;i<=n;i++)
        if (smn[i]==0)
            printf("+");
        else
            printf("-");
    return 0;
}