Cod sursa(job #460115)

Utilizator katakunaCazacu Alexandru katakuna Data 1 iunie 2010 11:47:47
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.09 kb
#include<stdio.h>
#include<cstdlib>
#include<ctime>

long long a[50011],n,i,p[50011],P,m[50011],M,sol[50011];
long long s,S;


int main(){


FILE *f=fopen("semne.in","r");
fscanf(f,"%lld %lld",&n,&S);
long long x;

    for(i=1;i<=n;i++){
    fscanf(f,"%lld",&a[i]);
    x=a[i];
    
       if(s <= S){
       P++;
       p[P] = i;

       sol[i]=1;
       s+=x;
       }

       else{
       M++;
       m[M] = i;
       sol[i]=0;
       s-=x;
       }

    }
    
fclose(f);

srand(time(0));

    while( S!=s ){
       if(S < s){
       x=(rand()%P) + 1;
       s-=((long long)a[p[x]])<<1;
       sol[p[x]]=0;
       M++;
       m[M]=p[x];
       p[x]=p[P];
       p[P]=0;
       P--;
       }

       else{
       x=(rand()%M) + 1;
       s+=((long long)a[m[x]])<<1;
       sol[m[x]]=1;
       P++;
       p[P]=m[x];
       m[x]=m[M];
       m[M]=0;
       M--;
       }
       
    }


FILE *g=fopen("semne.out","w");

  for(i=1;i<=n;i++)
   if(sol[i])
   fprintf(g,"+");


   else
   fprintf(g,"-");
     
fclose(g);

return 0;
}