Cod sursa(job #3142817)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 24 iulie 2023 17:53:17
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("semne.in");
ofstream fout("semne.out");
int a[50002], n;
int P[50002], np, M[50002], nm;
char sol[50002];
int main()
{
    int i, j;
    long long s, suma;
    fin >> n >> s;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    srand(time(0));
    suma = 0;
    for (i = n; i >= 1; i--)
        if (suma < s)
        {
            suma += a[i];
            P[np++] = i;
        }
        else
        {
            suma -= a[i];
            M[nm++] = i;
        }
    while (suma != s)
    {
        if (suma < s)
        {
            j = rand() % nm;
            suma = suma + 2 * a[M[j]];
            P[np++] = M[j];
            M[j] = M[nm - 1];
            nm--;
        }
        else
        {
            j = rand() % np;
            suma = suma - 2 * a[P[j]];
            M[nm++] = P[j];
            P[j] = P[np - 1];
            np--;
        }
    }
    for (i = 1; i <= n; i++)
        sol[i] = '+';
    for (i = 0; i < nm; i++)
        sol[M[i]] = '-';
    fout << (sol + 1) << "\n";
    fout.close();
    return 0;
}