Cod sursa(job #340982)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 17 august 2009 11:19:00
Problema Semne Scor 5
Compilator cpp Status done
Runda Summer Camp #5 Marime 1.69 kb
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define DIM 50005
int n,s,a[DIM],v1[DIM],v2[DIM],q1,q2,s2;
int read ()
{
    int i;
    scanf("%d%d",&n,&s);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if(s2<=s)
            s2+=a[i],v1[++q1]=i;
        else
            s2-=a[i],v2[++q2]=i;       
    }    
}
int check (int x)
{
    int i;
    if(q1<q2)
    {
        for(i=1;i<=q1;++i)
            if(a[x]==v1[i])
                return 1;
        return 2;
    }
    else
    {
        for(i=1;i<=q2;++i)
            if(a[x]==v2[i])
                return 2;
        return 1;
    }
}
void show ()
{
    int i;
    for(i=1;i<=n;++i)
        if(check(i)==1)
            printf("+");
        else
            printf("-");
    printf("\n");
}
void solve (int sir,int shit)
{
    int i;
    if(sir==1)
    {
        for(i=1;i<=q2+1;++i)
        {
            if(i==q2+1)
                ++q2;
            if(v2[i]==0)
            {
                v2[i]=v1[shit];break;
            }
        }
            
        v1[shit]=0;
        s2=s2-a[v2[q2]]-a[v2[q2]];
    }
    else
    {
        for(i=1;i<=q1+1;++i)
        {
            if(i==q1+1)
                ++q1;
            if(v1[i]==0)
            {
                v1[i]=v2[shit];break;
            }
        }
        v2[shit]=0;
        s2=s2+a[v1[q1]]+a[v1[q1]];
    }
}
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;
}