Cod sursa(job #2787394)

Utilizator VladPislaruPislaru Vlad Rares VladPislaru Data 23 octombrie 2021 10:48:40
Problema Semne Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;


/**

Algoritmi randomizati


NP-complete

*/

ifstream fin ("semne.in");
ofstream fout ("semne.out");

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