Cod sursa(job #71301)

Utilizator floringh06Florin Ghesu floringh06 Data 10 iulie 2007 00:31:16
Problema Semne Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
using namespace std;
#define MAX_N 50005
#include <stdio.h>
#include <fstream>
#define Vmax 5000005

int n,i,sp,sm,s,dif,val=-1;
int 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 %d\n",&n,&s);
    memset(p,0,sizeof(p));
    for (i=1; i<=n; i++)
    {
     fscanf(fin,"%d",a+i);
     sp+=a[i]; p[i]=1;
     pls[a[i]]++;
    }
    int c;
    
    while (sp!=s) 
     {
      c=rand() % 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;
}