Cod sursa(job #1250034)

Utilizator rangerChihai Mihai ranger Data 27 octombrie 2014 19:27:04
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<ctime>
#include<cstdlib>
using namespace std;

const int nmax=50001;
int n,a[nmax],i,p[nmax],m[nmax],P,M,x;
long long sum,s;

int main()
{
    ifstream cin("semne.in");
    ofstream cout("semne.out");

    cin >> n >> sum;

    for (i=1;i<=n;i++)
    {
        cin>>a[i];
        x=rand()%2;
        if (x) p[++P]=i,s+=a[i];
         else m[++M]=i,s-=a[i];
    }

    while (s!=sum)
    {
        if (s>sum)
        {
            do x=rand()%(P+1); while (!x);
            s-=2*a[p[x]];
            m[++M]=p[x];
            p[x]=p[P--];
        } else
        {
            do x=rand()%(M+1); while (!x);
            s+=2*a[m[x]];
            p[++P]=m[x];
            m[x]=m[M--];
        }
    }

    for (i=1;i<=P;i++) a[p[i]]=1;
    for (i=1;i<=M;i++) a[m[i]]=0;
    for (i=1;i<=n;i++)
        if (a[i])cout<<"+";
         else cout<<"-";
    return 0;
}