Cod sursa(job #2011024)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 14 august 2017 22:34:55
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>
#define Nmax 50001
using namespace std;
char a[Nmax];
long long v[Nmax];
vector <long long> pls;
vector <long long> mins;
int main()
{
    FILE *f=freopen("semne.in","r",stdin);
    FILE *g=freopen("semne.out","w",stdout);
    long long n,s,sum=0,i,x;
    scanf("%lld %lld",&n,&s);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&v[i]);
        if(sum<s)
        {
            sum+=v[i];
            pls.push_back(i);
            a[i]='+';
        }
        else
        {
            sum-=v[i];
            mins.push_back(i);
            a[i]='-';
        }
    }
    srand(time(NULL));
    while(sum!=s)
    {
        if(sum<s)
        {
            x=rand()%mins.size();
            sum+=2*v[mins[x]];
            pls.push_back(mins[x]);
            a[mins[x]]='+';
            mins[x]=mins.back();
            mins.pop_back();
        }
        else
        {
            x=rand()%pls.size();
            sum-=2*v[pls[x]];
            mins.push_back(pls[x]);
            a[pls[x]]='-';
            pls[x]=pls.back();
            pls.pop_back();
        }
    }
        printf("%s\n",a+1);

    return 0;
}