Cod sursa(job #968028)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 29 iunie 2013 19:27:10
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <ctime>

using namespace std;

int main()
{
    ifstream fin("semne.in");
    ofstream fout("semne.out");

    srand(time(0));
    long long int s;
    int n;
    int i;
    int a[50005];
    int p[50005];
    int m[50005];
    int sol[50005];
    int lp=0;
    int lm=0;
    int x;
    long long int sum=0;

    fin>>n>>s;
    for(i=0;i<n;i++)
    {
        fin>>a[i];
        x=rand()%2;
        sol[i]=x;
        if(!x)
        {
            sum+=(a[i]*1ll);
            p[lp++]=i;
        }
        else
        {
            sum-=(a[i]*1ll);
            m[lm++]=i;
        }
    }

    while(sum!=s)
    {
        if(sum>s)
        {
            x=rand()%lp;
            sum-=(2ll*a[p[x]]);
            m[lm++]=p[x];
            sol[p[x]]=1-sol[p[x]];
            swap(p[x],p[--lp]);
        }
        else
        {
            x=rand()%lm;
            sum+=(2ll*a[m[x]]);
            p[lp++]=m[x];
            sol[m[x]]=1-sol[m[x]];
            swap(m[x],m[--lm]);
        }
    }
    for(i=0;i<n;i++)
    {
        if(sol[i]==0)
            fout<<'+';
        else
            fout<<'-';
    }
    fout<<'\n';

    fin.close();
    fout.close();
    return 0;
}