Cod sursa(job #256483)

Utilizator ConsstantinTabacu Raul Consstantin Data 11 februarie 2009 20:15:27
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#include<stdlib.h>
#include<ctime>
long long x[500001],p[500001],m[500001],sol[50001],P,M,i,j,k,l,n,s,sum;
int main(){
FILE *f=fopen("semne.in","r");
fscanf(f,"%lld %lld",&n,&sum);
for(i=1;i<=n;i++)
        {fscanf(f,"%lld",&x[i]);
        if(s<sum)
                {p[++P]=i;
                s+=x[i];
                sol[i]=1;
                }
        else
                {m[++M]=i;
                s-=x[i];
                sol[i]=0;
                }
        }
while(s!=sum)
        {while(s<sum)
                {k=rand()%M+1;
                s+=x[m[k]]<<1;
                sol[m[k]]=1;
                p[++P]=m[k];
                m[k]=m[M];
                M--;}
      while(s>sum)
        {k=rand()%P+1;
        s-=x[p[k]]<<1;
        sol[p[k]]=0;
        m[++M]=p[k];
        p[k]=p[P];
        P--;
        }
   }
FILE *g=fopen("semne.out","w");
for(i=1;i<=n;i++)
        if(sol[i]==1)
                fprintf(g,"%c",'+');
        else
                fprintf(g,"%c",'-');
fclose(f);
fclose(g);
return 0;}