Cod sursa(job #2015347)

Utilizator amaliarebAmalia Rebegea amaliareb Data 25 august 2017 20:26:57
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;
int n,i,j,v[50005],poz;
long long s,S;
char semn[50005];
vector<int> pluss,minuss;
ifstream f("semne.in");
ofstream g("semne.out");


int main()
{
    f>>n>>S;
    s=0;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
        if(s<S)
        {
            semn[i]='+';
            pluss.push_back(i);
            s+=v[i];
        }
        else
        {
            semn[i]='-';
            minuss.push_back(i);
            s-=v[i];
        }
    }
    srand(time(0));
    while(s!=S)
    {
        if(s>S)
        {
            poz=rand()%pluss.size();
            s-=2*v[pluss[poz]];
            semn[pluss[poz]]='-';
            minuss.push_back(pluss[poz]);
            pluss[poz]=pluss.back();
            pluss.pop_back();
        }
        else
        {
            poz=rand()%minuss.size();
            s+=2*v[minuss[poz]];
            semn[minuss[poz]]='+';
            pluss.push_back(minuss[poz]);
            minuss[poz]=minuss.back();
            minuss.pop_back();
        }
    }
    for(i=1;i<=n;i++) g<<semn[i];
    g<<'\n';
    return 0;
}