Cod sursa(job #340995)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 17 august 2009 11:39:11
Problema Semne Scor 100
Compilator cpp Status done
Runda Summer Camp #5 Marime 1.22 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define DIM 50005
#define mm long long 
int n,q1,q2;
mm a[DIM],v1[DIM],v2[DIM],fmm[DIM],s2,s;
int read ()
{
    int i;
    scanf("%lld%lld",&n,&s);
    for(i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        if(s2<s)
        {
            s2+=a[i];
            fmm[i]=1;
            v1[++q1]=i;
        }
        else
            s2-=a[i],v2[++q2]=i;       
    }    
}
void show ()
{
    int i;
    for(i=1;i<=n;++i)
        if(fmm[i])
            printf("+");
        else
            printf("-");
}
void solve (int sir,int shit)
{
    int i;
    if(sir==1)
    {
        s2=s2-a[v1[shit]]-a[v1[shit]];
        fmm[v1[shit]]=0;
        v2[++q2]=v1[shit];
        v1[shit]=v1[q1--];
    }
    else
    {
        s2=s2+a[v2[shit]]+a[v2[shit]];
        fmm[v2[shit]]=1;
        v1[++q1]=v2[shit];
        v2[shit]=v2[q2--];
    }
}
int main ()
{
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    srand(time(0));
    read ();
    while(s2!=s)
    {
        if(s2>s)
            solve(1,rand()%q1+1);
        else
            solve(2,rand()%q2+1);
    }
    show ();
    return 0;
}
//1-poz 2-neg