Cod sursa(job #1557460)

Utilizator EuEricCiordel Rromeo EuEric Data 27 decembrie 2015 16:15:53
Problema Semne Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<fstream>
#include<cstdlib>
#include<ctime>
#include<vector>
using namespace std;
int ve[50005];
bool semn[50005];
int main()
{
    ifstream cin("semne.in");
    ofstream cout("semne.out");
    vector<int> plus;
    vector<int> minus;
    srand(time(0));
    int n,x,s;
    long long suma=0;
    cin>>n>>s;
    for(int i=1;i<=n;++i)
    {
        cin>>ve[i];
        if(rand() % 2 ==1){
            plus.push_back(i);
            suma+=ve[i];
            semn[i]=1;
        }
        else
        {
            minus.push_back(i);
            suma-=ve[i];
            semn[i]=0;
        }
    }
     while(suma!=s)
    {
        if(suma>s)
        {
           x=rand() % plus.size();
           semn[plus[x]]=0;
           minus.push_back(plus[x]);
           suma=suma-2*ve[plus[x]];
           swap(plus[x],plus[plus.size()-1]);
           plus.pop_back();
        }
        if(suma<s)
        {
            x=rand() % minus.size();
            semn[minus[x]]=1;
            plus.push_back(minus[x]);
            suma+=2*ve[minus[x]];
            swap(minus[x],minus[minus.size()-1]);
            minus.pop_back();
        }
    }
    for(int i=1;i<=n;++i)
    {
        if(semn[i]==1)
            cout<<"+";
        else
            cout<<"-";
    }
    return 0;
}