Cod sursa(job #986129)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 17 august 2013 19:16:53
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>

using namespace std;

#define Nmax 50005

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

void read()
{
    ifstream f("semne.in");
    f>>N>>S;
    bool r;
    srand(time(0));
    for(int i = 1;i <= N; ++i)
    {
        f >> v[i];
        r = rand()%2;
        semne[i] = r;
        if(r)
        {
            suma += v[i];
            pozi[++pozi[0]] = i;
        }
        else
        {
            suma -= v[i];
            nega[++nega[0]] = i;
        }
    }
}

void solve()
{
    int r;
    while(suma!=S)
    {
        if(suma<S)
        {
            r = (rand()%nega[0])+1;
            suma += 2*v[nega[r]];
            semne[nega[r]] = 1;
            pozi[++pozi[0]] = nega[r];
            nega[r] = nega[nega[0]--];
        }
        if(suma>S)
        {
            r = (rand()%pozi[0])+1;
            suma -= 2*v[pozi[r]];
            semne[pozi[r]] = 0;
            nega[++nega[0]] = pozi[r];
            pozi[r] = pozi[pozi[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;
}