Cod sursa(job #71310)

Utilizator floringh06Florin Ghesu floringh06 Data 10 iulie 2007 01:08:30
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
using namespace std;
#define MAX_N 50005
#include <stdio.h>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#define Vmax 5000005

int n,i;
long long s,dif,val=-1,sp;
long long a[MAX_N];
char p[MAX_N],semn;   
int pls[Vmax],mns[Vmax];

          
int main()
{   
FILE *fin=fopen("semne.in","r"),
     *fout=fopen("semne.out","w");

    fscanf(fin,"%d %lld\n",&n,&s);
    memset(p,0,sizeof(p));
    for (i=1; i<=n; i++)
    {
     fscanf(fin,"%lld",a+i);
     sp+=a[i]; p[i]=1;
     pls[a[i]]++;
    }
    
    srand ( time(NULL) );
    
    int c=n;
    
    while(sp>s) 
       {
       sp-= (a[c]<<1);     
       p[c]=0;
       pls[a[c]]--;
       mns[a[c]]++;
       c--;
       }
       
      dif=s-sp;
      if(dif%2==0)
         {
         dif/=2;
         if(dif>0 && dif<=5000000 && mns[dif]>0)
             {
             val=dif;
             semn=0;
             }
         if(dif<0 && dif>=-5000000 && pls[-dif]>0)
             {
             val=-dif;
             semn=1;
             }                     
         }

    
    while (sp!=s && val<0) 
     {
      c=rand();        
      if(c>33000) return 0;
      
      c%=n;
      p[c]^=1;        

      if(p[c])
         {
         sp+=(a[c]<<1);
         pls[a[c]]++;
         mns[a[c]]--;
         }
      else
         {
         sp-=(a[c]<<1);  
         pls[a[c]]--;
         mns[a[c]]++;
         }
                  
      dif=s-sp;
      if(dif%2==0)
         {
         dif/=2;
         if(dif>0 && dif<=5000000 && mns[dif]>0)
             {
             val=dif;
             semn=0;
             break;
             }
         if(dif<0 && dif>=-5000000 && pls[-dif]>0)
             {
             val=-dif;
             semn=1;
             break;
             }                     
         }
     }
     
    for (i=1; i<=n; i++) 
     if(a[i] == val && p[i] == semn)
        {
        p[i]^=1;
        val=-1;
        i--;     
        }
     else     
     if (p[i]==1) fprintf(fout,"+");
      else fprintf(fout,"-");                    
    
    fclose(fin); fclose(fout);  
      
    return 0;
}