Cod sursa(job #2922238)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 6 septembrie 2022 20:45:29
Problema Semne Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
/// Preset de infoarena
#include <fstream>
#include <vector>
#include <random>
#include <ctime>

using namespace std;

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

int n, v[50005];
vector <int> p, m;
long long sum, k;
mt19937 gen_rand(time(NULL));
bool semn[50005];

int main()
{
    fin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
        p.push_back(i);
        sum += v[i];
    }
    while(sum != k)
    {
        if(sum > k)
        {
            int poz = gen_rand() % p.size();
            swap(p[poz], p.back());
            sum -= 2 * v[p.back()];
            m.push_back(p.back());
            p.pop_back();
        }
        else
        {
            int poz = gen_rand() % m.size();
            swap(m[poz], m.back());
            sum += 2 * v[m.back()];
            p.push_back(m.back());
            m.pop_back();
        }
    }
    for(int elem : p)
        semn[elem] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(semn[i])
            fout << '+';
        else
            fout << '-';
    }
    return 0;
}