Cod sursa(job #362435)

Utilizator MKLOLDragos Ristache MKLOL Data 9 noiembrie 2009 18:52:34
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int N,S,nr,N1,N2;
long long v[50010],st[50010],dr[50010];
char a[50010];
long long Q,O;
int main()
{
freopen("semne.in","r",stdin);
 freopen("semne.out","w",stdout);
scanf("%d%d",&N,&S);

srand(time (0));

for(int i=0;i<N;++i)
{
    scanf("%lld",&v[i]);
    if(S>=Q)
    {
        a[i]=1;
        st[N1]=i;
        ++N1;
        Q=Q+v[i];
    }
    else if(S<Q)
    {
        a[i]=2;
        dr[N2]=i;
        ++N2;
        Q=Q-v[i];
    }

}

    while(Q!=S)
    {

        if(Q>S)
        {
        nr=rand()%N1;

        a[st[nr]]=2;

        Q=Q-v[st[nr]]-v[st[nr]];

        dr[N2]=st[nr];
        ++N2;
        st[nr]=st[N1-1];
        --N1;
        }

        else if(Q<S)
        {
        nr=rand()%N2;

        a[dr[nr]]=1;

        Q=Q+v[dr[nr]]+v[dr[nr]];

        st[N1]=dr[nr];
        ++N1;
        dr[nr]=dr[N2-1];
        --N2;
        }
}
for(int i=0;i<N;++i)
if(a[i]==1)
printf("+");
else printf("-");

return 0;
}