Cod sursa(job #1950186)

Utilizator andreiudilaUdila Andrei andreiudila Data 2 aprilie 2017 19:41:07
Problema Semne Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("semne.in");
ofstream fout("semne.out");
int v[50005], q,i,j,n,x;
char sol[50005];
int p[50005],m[50005],P,M;
long long sum,s;

int main()
{
    srand(time(NULL));

    fin>>n>>s;
    //sum=-s;

    for(i=1; i<=n; ++i)
    {
        fin>>v[i];
        if(rand()%2)
        {
            sum+=v[i];
            p[++P]=i;
        }
        else
        {
            sum-=v[i];
            m[++M]=i;
        }
    }

    while(sum!=s)
    {
        if(sum>0)
        {
            x=rand()%P+1;
            sum-=(long long)2*v[p[x]];
            m[++M]=p[x];
            swap(p[x],p[P--]);

        }

        else
        {
            x=rand()%M+1;
            sum+=(long long)2*v[m[x]];
            p[++P]=m[x];
            swap(m[x],m[M--]);

        }


    }



    for(i=1; i<=P; ++i) sol[p[i]]='+';
    for(i=1; i<=M; ++i) sol[m[i]]='-';


    fout<<sol+1;

    return 0;
}