Cod sursa(job #1808426)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 17 noiembrie 2016 18:00:24
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define MAXN 50050

using namespace std;

int n, a[MAXN];
int pl[MAXN], mn[MAXN];
long long s, crt;
char sol[MAXN];

inline int get(int lo, int hi) /// [lo, hi)
{
    return lo + (rand() % (hi-lo));
}

void solve()
{
    while (crt != s)
    {
        if (crt < s)
        {
            int mine = get(1, mn[0]+1);
            crt += 2*a[mn[mine]];
            pl[++pl[0]] = mn[mine];
            sol[mn[mine]] = '+';
            mn[mine] = mn[mn[0]--];
        }
        else
        {
            int mine = get(1, pl[0]+1);
            crt -= 2*a[pl[mine]];
            mn[++mn[0]] = pl[mine];
            sol[pl[mine]] = '-';
            pl[mine] = pl[pl[0]--];
        }
    }
}

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

    srand(time(0));
    scanf("%d %lld", &n, &s);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (get(0, 2) & 1) {
            sol[i] = '+';
            pl[++pl[0]] = i;
            crt += a[i];
        }
        else {
            sol[i] = '-';
            mn[++mn[0]] = i;
            crt -= a[i];
        }
    }
    solve();
    printf("%s", sol+1);
    return 0;
}