Cod sursa(job #1787189)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 24 octombrie 2016 11:56:55
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#include <time.h>
using namespace std;
ifstream f("semne.in");
ofstream g("semne.out");
long long nr[50005],n;
char S[50005];
long long s;
vector <int> p;
vector <int> m;
long long sum=0;
void Read()
{
    int i;
    f>>n>>s;
    for(i=1;i<=n;i++)
    {
        f>>nr[i];
        if(sum<s)
        {
            S[i]='+';
            p.push_back(i);
            sum+=nr[i];
        }
        else
        {
            S[i]='-';
            m.push_back(i);
            sum-=nr[i];
        }
    }
}

void Solve()
{
    srand (time(NULL));
    while(sum!=s)
    {
        if(sum<s)
        {
            int ind=rand()%m.size();
            sum+=2*(nr[m[ind]]);
            S[m[ind]]='+';
            p.push_back(m[ind]);
            m[ind]=m[m.size()-1];
            m.pop_back();
        }
        else
        {
            int ind=rand()%p.size();
            sum-=2*(nr[p[ind]]);
            m.push_back(p[ind]);
            S[p[ind]]='-';
            p[ind]=p[p.size()-1];
            p.pop_back();
        }
    }
}
int main()
{
    Read();
    Solve();
    for(int i=1;i<=n;i++)
        g<<S[i];
    return 0;
}