Cod sursa(job #2338016)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 6 februarie 2019 21:38:30
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>

#include<cstdlib>

#include<iostream>

#include<ctime>

#include<queue>

#define x first

#define y second

#define DN 50005

using namespace std;

ifstream fin("semne.in");

ofstream fout("semne.out");

int n,a[DN],t,poz,nr1,f,nr2;

long long s,sum;

char r[DN];

pair<int,int>q1[DN];

pair<int,int> q2[DN];

int main()

{

    fin>>n>>s;

    srand(time(0));

    for(int i=1;i<=n;i++)

    {

        fin>>a[i];

        sum+=a[i];

        r[i]='+';

        nr1++;

        q1[nr1].x=a[i];

        q1[nr1].y=i;

    }

    while(sum!=s)

    {

        if(sum>s)

        {

            t=rand()%nr1+1;

            sum-=2*q1[t].x;

            r[q1[t].y]='-';

            nr2++;

            q2[nr2]=q1[t];

            q1[t]=q1[nr1];

            nr1--;

        }

        else

        {

            t=rand()%nr2+1;

            sum+=2*q2[t].x;

            r[q2[t].y]='+';

            nr1++;

            q1[nr1]=q2[t];

            q2[t]=q2[nr2];

            nr2--;

        }

    }

    for(int i=1;i<=n;i++)

        fout<<r[i];

}