Cod sursa(job #340960)

Utilizator DraStiKDragos Oprica DraStiK Data 17 august 2009 10:15:01
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DIM 50005
#define tip long long

tip a[DIM],neg[DIM],poz[DIM];
int n,nneg,npoz;
int rez[DIM];
tip s,sum;

void read ()
{
    int i;

    scanf ("%d%lld",&n,&s);
    for (i=1; i<=n; ++i)
    {
        scanf ("%lld",&a[i]);
        if (sum<s)
        {
            sum+=a[i];
            rez[i]=1;
            poz[++npoz]=i;
        }
        else
        {
            sum-=a[i];
            neg[++nneg]=i;
        }
    }
}

void solve ()
{
    int i;

    for (; sum!=s; )
        if (sum<s)
        {
            i=rand ()%nneg+1;
            sum+=2*a[neg[i]];
            rez[neg[i]]=1;
            poz[++npoz]=neg[i];
            neg[i]=neg[nneg--];
        }
        else
        {
            i=rand ()%npoz+1;
            sum-=2*a[poz[i]];
            rez[poz[i]]=0;
            neg[++nneg]=poz[i];
            poz[i]=poz[npoz--];
        }
}

void print ()
{
    int i;

    for (i=1; i<=n; ++i)
        if (rez[i])
            printf ("+");
        else
            printf ("-");
}

int main ()
{
    freopen ("semne.in","r",stdin);
    freopen ("semne.out","w",stdout);
    srand (time (0));

    read ();
    solve ();
    print ();

    return 0;
}