Cod sursa(job #1471533)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 14 august 2015 11:50:28
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
/*http://www.infoarena.ro/problema/semne*/
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define N 50002

using namespace std;

struct nums
{
    int x, poz;
} sub[N], add[N];

int v[N], i, n, poz, p, m;
long long s, sum;
bool semn[N];

int main()
{
    ifstream f("semne.in");
    ofstream g("semne.out");

    srand(time(NULL));
    f >> n >> s;
    for(i=1; i<=n; ++i)
    {
        f >> v[i];
        poz = rand() % 2;
        if(poz)
        {
            sum += v[i];
            add[++p].x = v[i];
            add[p].poz = i;
        }
        else
        {
            sum -= v[i];
            sub[++m].x = v[i];
            sub[m].poz = i;
        }
    }

    while(sum != s)
    {
        if(sum < s)
        {
            poz = 1 + rand() % m;
            add[++p] = sub[poz];
            sum += 2*sub[poz].x;
            swap(sub[poz], sub[m--]);
        }
        else
        {
            poz = 1 + rand() % p;
            sub[++m] = add[poz];
            sum -= 2*add[poz].x;
            swap(add[poz], add[p--]);
        }
    }
    for(i=1; i<=m; ++i)
        semn[sub[i].poz] = 1;

    for(i=1; i<=n; ++i)
        if(semn[i]) g << "-";
        else g << "+";
    f.close();
    g.close();
    return 0;
}