Cod sursa(job #2787391)

Utilizator CatalinCosminGirgoriu Cosmin CatalinCosmin Data 23 octombrie 2021 10:48:23
Problema Semne Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
/**
Algoritmi randomizati

NP-complete
*/
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) /// iau un element din M[]
        {
            j = rand() % nm;
            suma = suma + 2 * a[M[j]];
            P[np++] = M[j];
            M[j] = M[nm - 1];
            nm--;
        }
        else /// suma > s
        {
            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;
}