Cod sursa(job #1293248)

Utilizator danalex97Dan H Alexandru danalex97 Data 15 decembrie 2014 16:59:50
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

ifstream F("semne.in");
ofstream G("semne.out");

const int N = 50010;

int n,v[N],ans[N];
long long ss,s[2];
vector<int> a[2];

int main()
{
    srand(time(0));
    F>>n>>ss;
    for (int i=1;i<=n;++i)
    {
        F>>v[i];
        int x = rand()%2;
        a[x].push_back(i);
        s[x] += v[i];
    }
    while ( s[0] - s[1] != ss )
    {
        int x = 0 , y = 1;
        if ( s[0] - s[1] > ss )
            x = 0 , y = 1;
        else
            x = 1 , y = 0;

        int pl = rand() % int(a[x].size());

        swap(a[x][pl],a[x].back());
        s[x] -= v[a[x].back()];
        s[y] += v[a[x].back()];
        a[y].push_back( a[x].back() );
        a[x].pop_back();
    }
    for (int x=0;x<2;++x)
        for (int i=0;i<int(a[x].size());++i)
            ans[a[x][i]] = x;
    for (int i=1;i<=n;++i)
        if ( ans[i] == 0 )
            G<<"+";
        else
            G<<"-";
    G<<'\n';
}