Cod sursa(job #680208)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 14 februarie 2012 12:17:35
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.04 kb
#include <cstdio>
#include <ctime>
#include <algorithm>

using namespace std;

#define maxn 50010

int n, x, v[maxn];
int p0, m0, p[maxn], m[maxn];
char sol[maxn];
long long sc, s;

int main()
{
    srand(time(0));

    freopen("semne.in", "r", stdin);
    freopen("semne.out", "w", stdout);

    scanf("%d%lld", &n, &s);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &v[i]);
        if(rand()%2)
        {
            m[++m0]=i;
            sol[i]='-';
            sc-=v[i];
        }
        else
        {
            p[++p0]=i;
            sol[i]='+';
            sc+=v[i];
        }
    }

    while(sc!=s)
    {
        if(sc<s)
        {
            x=rand()%m0+1;
            swap(m[x], m[m0]);
            p[++p0]=m[m0];
            sc=sc+2*v[m[m0]];
            sol[m[m0]]='+';
            --m0;
        }
        else
        {
            x=rand()%p0+1;
            swap(p[x], p[p0]);
            m[++m0]=p[p0];
            sc=sc-2*v[p[p0]];
            sol[p[p0]]='-';
            --p0;
        }
    }

    printf("%s", sol+1);

    return 0;
}