Cod sursa(job #2164369)

Utilizator akaprosAna Kapros akapros Data 12 martie 2018 23:13:16
Problema Semne Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>
#define maxN 50002
#define ll long long
using namespace std;

FILE *fin = freopen("semne.in", "r", stdin);
FILE *fout = freopen("semne.out", "w", stdout);

int n;

ll s;
int v[maxN];
bool sgn[maxN];

vector < short int > A, B;

ll sum;

int main()
{
    scanf("%d %lld", &n, &s);
    for (int i = 1; i <= n; ++ i)
    {
        scanf("%d", &v[i]);
        sgn[i] = rand() & 1;
        if (sgn[i])
        {
            sum += v[i];
            A.push_back(i);
        }
        else
        {
            sum -= v[i];
            B.push_back(i);
        }
    }

    while (sum != s)
    {
        if (sum < s)
        {
            int it = rand() % B.size();
            sgn[B[it]] = !sgn[B[it]];
            A.push_back(B[it]);
            sum += 2LL * v[B[it]];
            swap(B[it], B.back());
            B.pop_back();
        }
        else
        {
            int it = rand() % A.size();
            sgn[A[it]] = !sgn[A[it]];
            B.push_back(A[it]);
            sum -= 2LL * v[A[it]];
            swap(A[it], A.back());
            A.pop_back();
        }
    }

    for (int i = 1; i <= n; ++ i)if (sgn[i]) printf("+");
        else
            printf("-");
    return 0;
}