Cod sursa(job #984797)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 15 august 2013 15:08:47
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <bitset>
#define In "semne.in"
#define Out "semne.out"
#define Nmax 50005
using namespace std;

int N, v[Nmax],s0[Nmax],s1[Nmax];
bitset<Nmax>sol;
long long S,sum;
inline void Read()
{
    ifstream f(In);
    f>>N>>S;
    bool r;
    srand(time(0));
    for(int i = 1;i <= N; ++i)
    {
        f>>v[i];
        r = rand()%2;
        sol[i] = r;
        if(r)
        {
            sum += v[i];
            s1[++s1[0]] = i;
        }
        else
        {
            sum -= v[i];
            s0[++s0[0]] = i;
        }
    }
}

inline void Solve()
{
    int r;
    while(sum!=S)
    {
        if(sum<S)
        {
            r = (rand()%s0[0])+1;
            sum += 2*v[s0[r]];
            sol[s0[r]] = 1;
            s1[++s1[0]] = s0[r];
            s0[r] = s0[s0[0]--];
        }
        if(sum>S)
        {
            r = (rand()%s1[0])+1;
            sum -= 2*v[s1[r]];
            sol[s1[r]] = 0;
            s0[++s0[0]] = s1[r];
            s1[r] = s1[s1[0]--];
        }
    }
}

inline void Write()
{
    ofstream g(Out);
    for(int i = 1;i <= N; ++i)
        g<<(sol[i]?"+":"-");
    g<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}