Cod sursa(job #1729534)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 15 iulie 2016 00:41:12
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream in("semne.in");
ofstream out("semne.out");
const int maxn = 50005;
int sir1[maxn];
int sir2[maxn];
int v[maxn];
int n, lg1, lg2;
long long sum, s;

void _move_(bool ok)
{
    if(ok == 1)
    {
        int poz = rand() % lg1 + 1;
        swap(sir1[poz], sir1[lg1]);
        sir2[++lg2] = sir1[lg1];
        sum = sum - 2 * v[sir1[lg1]];
        lg1--;
    }
    else
    {
        int poz = rand() % lg2 + 1;
        swap(sir2[poz], sir2[lg2]);
        sir1[++lg1] = sir2[lg2];
        sum = sum + 2 * v[sir2[lg2]];
        lg2--;
    }
}

int main()
{
    in >> n >> s;
    srand(time(0));
    for(int i = 1; i <= n; i++)
    {
        in >> v[i];
        if(sum < s)
        {
            sir1[++lg1] = i;
            sum += v[i];
        }
        else
        {
            sir2[++lg2] = i;
            sum -= v[i];
        }
    }
    while(sum != s)
    {
        if(sum < s)
            _move_(0);
        else
            _move_(1);
    }
    sort(sir1 + 1, sir1 + lg1 + 1);
    sort(sir2 + 1, sir2 + lg2 + 1);
    int poz1 = 1;
    int poz2 = 1;
    while(poz1 <= lg1 && poz2 <= lg2)
    {
        if(v[sir1[poz1]] < v[sir2[poz2]])
        {
            out << '+';
            poz1++;
        }
        else
        {
            out << '-';
            poz2++;
        }
    }
    while(poz1 <= lg1)
    {
        poz1++;
        out << '+';
    }
    while(poz2 <= lg2)
    {
        poz2++;
        out << '-';
    }
    out << "\n";
    return 0;
}