Cod sursa(job #1071053)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 ianuarie 2014 15:05:24
Problema Semne Scor 95
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.3 kb
#include <algorithm>
#include <fstream>
#include <bitset>
#include <cstdlib>
#include <vector>
#include <ctime>

using namespace std;

const int N=50005;

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

int a[N];
bitset <N> semn;
vector <int> pluss, minuss;

int main()
{
    int n, i, poz;
    long long m, s=0;
    fin>>n>>m;
    srand(time(0));
    for(i=1;i<=n;i++)
    {
        fin>>a[i];
        semn[i]=rand()&1;
        if(semn[i])
        {
            pluss.push_back(i);
            s+=a[i];
        }
        else
        {
            minuss.push_back(i);
            s-=a[i];
        }
    }
    while(s!=m)
    {
        if(s>m)
        {
            poz=rand()%pluss.size();
            semn[pluss[poz]]=0;
            s-=2*a[pluss[poz]];
            minuss.push_back(pluss[poz]);
            pluss[poz]=pluss.back();
            pluss.pop_back();
        }
        else
        {
            poz=rand()%minuss.size();
            semn[minuss[poz]]=1;
            s+=2*a[minuss[poz]];
            pluss.push_back(minuss[poz]);
            minuss[poz]=minuss.back();
            minuss.pop_back();
        }
    }
    for(i=1;i<=n;i++)
    {
        if(semn[i]) fout<<"+";
        else fout<<"-";
    }
    fin.close();
    fout.close();
}