Cod sursa(job #2022684)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 16 septembrie 2017 22:49:04
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.26 kb
#include<bits/stdc++.h>
#define maxN 50005
using namespace std;
char semn[maxN];
int v[maxN],n,ind;
long long s,sum;
vector<int> add,substract;
int main()
{
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    scanf("%d%lld",&n,&sum);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        if(s<sum)
        {
            semn[i]='+';
            s=s+1LL*v[i];
            add.push_back(i);
        }
            else
        {
            semn[i]='-';
            s=s-1LL*v[i];
            substract.push_back(i);
        }
    }
    srand(time(0));
    while(s!=sum)
    {
        if(s>sum)
        {
            ind=rand()%add.size();
            s-=2*v[add[ind]];
            semn[add[ind]]='-';
            substract.push_back(add[ind]);
            add[ind]=add.back();
            add.pop_back();
        }
            else
        if(s<sum)
        {
            ind=rand()%substract.size();
            s+=2*v[substract[ind]];
            semn[substract[ind]]='+';
            add.push_back(substract[ind]);
            substract[ind]=substract.back();
            substract.pop_back();
        }
    }
    for(int i=1;i<=n;i++)
        printf("%c",semn[i]);
    printf("\n");
    return 0;
}