Cod sursa(job #986134)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 17 august 2013 19:31:21
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

#define Nmax 50005

long long N, S, suma;
int a[Nmax];
int pozi[Nmax], nega[Nmax];
int semne[Nmax];

void read()
{
    ifstream f("semne.in");

    f >> N >> S;

    srand( time( NULL ) );

    for ( int i = 1; i <= N; ++i )
    {
        f >> a[i];

        suma += a[i] * 1LL;
        pozi[ ++pozi[0] ] = i;
        semne[i] = 1;
    }

    f.close();
}

void solve()
{
    while( suma != S )
    {
        if ( suma > S )
        {
            int ind = ( rand() % pozi[0] ) + 1;

            semne[ind] = -1;
            suma -= 2 * a[pozi[ind]];
            nega[ ++nega[0] ] = pozi[ind];
            pozi[ind] = pozi[ pozi[0]-- ];
        }
        else
        {
            int ind = ( rand() % nega[0] ) + 1;

            semne[ind] = 1;
            suma += 2 * a[nega[ind]];
            pozi[ ++pozi[0] ] = nega[ind];
            nega[ind] = nega[ nega[0]-- ];
        }
    }
}

void print()
{
    ofstream g("semne.out");

    for ( int i = 1; i <= N; ++i )
    {
        if ( semne[i] == 1 )
                g << "+";
        else
                g << "-";
    }

    g << "\n";

    g.close();
}

int main()
{
    read();
    solve();
    print();

    return 0;
}