Cod sursa(job #1869658)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 6 februarie 2017 01:21:43
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.43 kb
#include <fstream>
#include <vector>
#include <cstdlib>
#include <time.h>
using namespace std;
ifstream f("semne.in");
ofstream g("semne.out");
long long Numbers[50005],N;
char Sign[50005];
long long S;
vector <int> Plus;
vector <int> Minus;
long long currentsum=0;
void Read()
{
    int i;
    f>>N>>S;
    for(i=1;i<=N;i++)
    {
        f>>Numbers[i];
        if(currentsum<S)
        {
            Sign[i]='+';
            Plus.push_back(i);
            currentsum+=Numbers[i];
        }
        else
        {
            Sign[i]='-';
            Minus.push_back(i);
            currentsum-=Numbers[i];
        }
    }
}

void findSign()
{
    int i;
    srand (time(NULL));
    while(currentsum!=S)
    {
        if(currentsum<S)
        {
            int index=rand()%Minus.size();
            currentsum+=2*(Numbers[Minus[index]]);
            Sign[Minus[index]]='+';
            Plus.push_back(Minus[index]);
            Minus[index]=Minus[Minus.size()-1];
            Minus.pop_back();
        }
        else
        {
            int index=rand()%Plus.size();
            currentsum-=2*(Numbers[Plus[index]]);
            Minus.push_back(Plus[index]);
            Sign[Plus[index]]='-';
            Plus[index]=Plus[Plus.size()-1];
            Plus.pop_back();
        }
    }
}
int main()
{
    Read();
    findSign();
    for(int i=1;i<=N;i++)
        g<<Sign[i];
    return 0;
}