Cod sursa(job #71406)

Utilizator floringh06Florin Ghesu floringh06 Data 10 iulie 2007 14:22:05
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
using namespace std;

#include <cstdio>
//#include <time.h>
#include <cstdlib>

  #define ll long long
  #define MAX_N 50005
  #define MAX_V 5000005

int a[MAX_N];
ll s[MAX_N],S,sc;
bool stat[MAX_N];
int n,i;

int searchplus(int x)
{  
  int i;
  bool ok=false;
  for (i=1; i<=n; i++)
   if (a[i]==x && stat[i]==false) 
    { ok = true; break; }
  if (ok==true) 
   {
     sc+=a[i]<<1;
     stat[i]=true;
     return 1;
   }
  return 0;
}       
   
int searchminus(int x)
{  
  int i;
  bool ok=false;
  for (i=1; i<=n; i++)
   if (a[i]==x && stat[i]==true) 
    { ok = true; break; }
  if (ok==true) 
   {
     sc+=a[i]<<1;
     stat[i]=false;
     return 1;
   }
  return 0;
}       


int main()
{
     freopen("semne.in","r",stdin);
     freopen("semne.out","w",stdout);
   
     scanf("%d %lld",&n,&S);
     
     for (i=1; i<=n; i++) 
       scanf("%d",a+i);
        
     s[n]=sc=a[n];
     
     for (i=n-1; i>=1; i--)
      { 
       sc +=(long long)a[i];
       s[i]=(long long)sc;
      }  
     sc=0;
//     srand(unsigned(time(NULL)));    
     int c=0,in=0;
     bool ok;
     for (i=1; i<=n; i++)
      {
         c=rand() % 2+1;
         if (sc+s[i]==S) 
          { 
            in=i; ok=true;
            break;
          }
         if (sc-s[i]==S)
          {
            in=i; ok=false;
            break;
          }                  
         if (c&1) {  stat[i]=true; sc+=a[i]; }

          else { stat[i]=false; sc-=a[i]; }
      }          
     
     if (in!=0)
      {
        if (ok==true)
           for (i=in; i<=n; i++)
            stat[i]=true;
        else 
           for (i=in; i<=n; i++) 
            stat[i]=false;
        for (i=1; i<=n; i++)
          if (stat[i]==true) printf("+");
            else printf("-");
        
        return 0;
      }
     else
      while (sc!=S)
       {
         while (sc<S)
          {
            c=rand()%n;
            if ((S-sc)&1==0)
             if (searchplus((S-sc)>>1)) break;
            if (stat[c]==false) 
             { 
                sc+=a[c]<<1;
                stat[c]=true;
             }
          }                     
         while (sc>S)
          {
            c=rand()%n;
            if ((sc-S)&1==0)
             if (searchminus((sc-S)>>1)) break;
            if (stat[c]==true) 
             { 
                sc-=a[c]<<1;
                stat[c]=false;
             }
          }   
      }    
     for (i=1; i<=n; i++)
      if (stat[i]==true) printf("+");
       else printf("-");     
          
     fclose(stdin); 
     fclose(stdout);
     
     return 0;
}