Cod sursa(job #2024457)

Utilizator LucianTLucian Trepteanu LucianT Data 20 septembrie 2017 18:16:53
Problema Semne Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
const int maxN=5e4+4;

int v[maxN];
int sol[maxN];
int n,sum,curr;
vector<int> Plus;
vector<int> Minus;

int main()
{
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);

    scanf("%d %d",&n,&sum);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);

        if(rand()%2){
            curr+=v[i];
            Plus.push_back(i);
            sol[i]=1;
        }
        else{
            curr-=v[i];
            Minus.push_back(i);
            sol[i]=-1;
        }
    }

    while(curr!=sum)
        if(curr>sum)
        {
            int pos=rand()%Plus.size();
            curr-=2*v[Plus[pos]];
            sol[Plus[pos]]=-1;

            Minus.push_back(Plus[pos]);
            swap(Plus[pos],Plus.back());
            Plus.pop_back();
        }
        else
        {
            int pos=rand()%Minus.size();
            curr+=2*v[Minus[pos]];
            sol[Minus[pos]]=1;

            Plus.push_back(Minus[pos]);
            swap(Minus[pos],Minus.back());
            Minus.pop_back();
        }

    for(int i=1;i<=n;i++)
        if(sol[i]>0)
            printf("+");
        else printf("-");

    return 0;
}