Cod sursa(job #1959690)

Utilizator Daria09Florea Daria Daria09 Data 9 aprilie 2017 19:56:00
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
#define nmax 50005
using namespace std;
ifstream f("semne.in");
ofstream g("semne.out");
long long s;
bool x[nmax];
int n,a[nmax];
vector<int> pluss,minuss;
int main()
{
    f>>n>>s; long long sum=0;
    for(int i=0;i<n;i++)
    {
        f>>a[i];
        if(sum>s)
        {
            sum-=a[i];
            minuss.push_back(i);
        }
        else
        {
            sum+=a[i],
            x[i]=1;
            pluss.push_back(i);
        }
    }
    srand(time(0));
    while(s!=sum)
    {
        if(sum>s)
        {
            int c=rand()%pluss.size();
            x[pluss[c]]=0; sum-=2*a[pluss[c]];
            minuss.push_back(pluss[c]);
            pluss[c]=pluss.back();
            pluss.pop_back();
        }
        else
        {
            int c=rand()%minuss.size();
            x[minuss[c]]=1; sum+=2*a[minuss[c]];
            pluss.push_back(minuss[c]);
            minuss[c]=minuss.back();
            minuss.pop_back();
        }
    }
    for(int i=0;i<n;i++)
        if(x[i]==0)
            g<<'-';
        else
            g<<'+';
    return 0;
}