Cod sursa(job #1866086)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 2 februarie 2017 17:05:33
Problema Semne Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MaxN =50005;

ifstream fin("semne.in");
ofstream fout("semne.out");

int n,a[MaxN];
long long S,crt;
char s[MaxN];
vector<int> v[2];

int main()
{
    int i;
    srand(time(0));
    fin >> n >> S;
    for(i=0;i<n;++i)
    {
        fin >> a[i];
        if(crt < S)
        {
            v[1].push_back(i);
            s[i]='+';
            crt+=a[i];
        }
        else
        {
            v[0].push_back(i);
            s[i]='-';
        }
    }
    while(crt!=S)
    {
        int semn=crt > S;
        int pos = rand() % (int)v[semn].size();
        swap(v[semn][pos], v[semn].back());
        pos=v[semn].back();
        v[semn].pop_back();
        v[!semn].push_back(pos);
        if(semn)
        {
            crt -= a[pos] << 1;
            s[pos]='-';
        }
        else
        {
            crt += a[pos] << 1;
            s[pos]='+';
        }
    }
    fout << s << '\n';
    return 0;
}