Cod sursa(job #1233318)

Utilizator touristGennady Korotkevich tourist Data 25 septembrie 2014 09:31:48
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <queue>
#define Nmax 50005

using namespace std;

int a[Nmax],sol[Nmax],Minus[Nmax],Plus[Nmax],nrP,nrM;

int main()
{
    int N,i,r,x,aux;
    long long S,suma=0;
    srand(time(0));
    freopen ("semne.in","r",stdin);
    freopen ("semne.out","w",stdout);
    scanf("%d%lld", &N,&S);
    for(i=1;i<=N;++i)
        scanf("%d", &a[i]);
    for(i=N;i;--i)
    {
        r=rand()%2;
        if(!r)
        {
            suma+=a[i];
            Plus[++nrP]=i;
        }
        else
        {
            suma-=a[i];
            Minus[++nrM]=i;
        }
    }
    while(suma!=S)
    {
        if(suma<S)
        {
            x=rand()%nrM+1;
            suma=suma+2*a[Minus[x]];
            Plus[++nrP]=Minus[x];
            Minus[x]=Minus[nrM--];
        }
        else
        {
            x=rand()%nrP+1;
            suma=suma-2*a[Plus[x]];
            Minus[++nrM]=Plus[x];
            Plus[x]=Plus[nrP--];
        }
    }
    for(i=1;i<=nrM;++i) sol[Minus[i]]=0;
    for(i=1;i<=nrP;++i) sol[Plus[i]]=1;
    for(i=1;i<=N;++i)
        if(!sol[i]) printf("-");
        else printf("+");
    printf("\n");
    return 0;
}