Cod sursa(job #71430)

Utilizator floringh06Florin Ghesu floringh06 Data 10 iulie 2007 15:03:50
Problema Semne Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
using namespace std;

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

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

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

void inc()
{
  int i = 1;
  while (sc < S && i <= n)
    {
      if (stat[i]==false)
       {
         stat[i] = true;
         sc += (a[i]<<1);
       }
      ++ i;
    }
}

void dec ()
{
  int i = n;
  while (sc > S && i >= 1)
    {
      if (stat[i]==true)
       {
         stat[i] = false;
         sc -= (a[i]<<1);
       }
      -- i;
    }
}

int main()
{
     freopen("semne.in","r",stdin);
     freopen("semne.out","w",stdout);
   
     scanf("%d %lld",&n,&S);
     
     for (i=1; i<=n; i++) 
       scanf("%lld",a+i);
        
     s[n]=sc=a[n];
     
     for (i=n-1; i>=1; i--)
      { 
       sc +=(long long)a[i];
       s[i]=(long long)sc;
      }  
     srand(unsigned(time(NULL)));    
     int c=0,in=0;
     bool ok;
     while (1)
     {
      sc=0;     
      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
       for (i=1; i<=80; i++)
        {
         if (sc<S) inc();
         if (sc>S) dec();
         if (sc==S) break;
        }  
      if (sc==S) break;
     }    
     for (i=1; i<=n; i++)
       if (stat[i]==true) printf("+");
        else printf("-");     
          
     fclose(stdin); 
     fclose(stdout);
     
     return 0;
}