Cod sursa(job #2478633)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 22 octombrie 2019 15:06:25
Problema Semne Scor 95
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stdlib.h>

using namespace std;

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

const int NMax = 5e4;

int N, V[NMax + 5];
long long S, K;

bool A[NMax + 5];
vector <int> Minus, Plus;

int main()
{
    fin >> N >> S;

    for(int i = 1; i <= N; i++)
    {
        fin >> V[i];

        if(K <= S)
            Plus.push_back(i), K += V[i];
        else
            Minus.push_back(i), K -= V[i];
    }

    while(K != S)
    {
        int poz = rand();

        if(K <= S && Minus.size() != 0)
        {
            poz = poz % Minus.size();

            Plus.push_back(Minus[poz]);
            Minus[poz] = Minus.back();
            Minus.pop_back();

            K += 2 * V[Plus.back()];
        }
        else
        {
            poz = poz % Plus.size();

            Minus.push_back(Plus[poz]);
            Plus[poz] = Plus.back();
            Plus.pop_back();

            K -= 2 * V[Minus.back()];
        }
    }
    for(auto x : Plus) A[x] = 1;

    for(int i = 1; i <= N; i++)
        fout << ((A[i]) ? '+' : '-');

    fout << '\n';

    fin.close();
    fout.close();

    return 0;
}