Cod sursa(job #2595280)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 7 aprilie 2020 14:47:17
Problema Semne Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;
int v[50010] , sol[50010];
vector <int> pls , mis;
int main()
{
    FILE *fin = fopen ("semne.in","r");
    FILE *fout = fopen ("semne.out","w");
    int n , i , pos , nr;
    long long s , sum=0;
    srand(time(0));
    fscanf (fin,"%d",&n);
    fscanf (fin,"%lld",&s);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
        sum += v[i];
        pls.push_back(i);
        sol[i] = 1;
    }
    while (sum != s){

        if (sum > s){ /// scot din plus bag in minus
            pos = rand() % pls.size();
            nr = pls[pos];
            sol[nr] = -sol[nr];
            pls.erase(pls.begin() + pos);
            mis.push_back(nr);
            sum -= 2 * v[nr];
        }
        else {
            pos = rand() % mis.size();
            nr = mis[pos];
            sol[nr] = -sol[nr];
            mis.erase(mis.begin() + pos);
            pls.push_back(nr);
            sum += 2 * v[nr];
        }

    }
    for (i = 1 ; i <= n ; i++){
        if (sol[i] == 1)
            fprintf (fout,"+");
        else fprintf (fout,"-");
    }
    return 0;
}