Cod sursa(job #50898)

Utilizator crawlerPuni Andrei Paul crawler Data 9 aprilie 2007 12:44:45
Problema Semne Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>
#include <time.h>

#define Nmax 50002
#define key 1234566691

typedef long long lint;

lint MOD = 1<<31;
lint a[Nmax], b[Nmax], v[Nmax];
lint r, p;
char s[Nmax];

void srand(lint seed)
 {
  r = 1+seed;      
 }

inline lint rand()
 {
  r+=key;
  if(r>MOD)
   r -= MOD; 
  return r;         
 }

int main()
 {
  freopen("semne.in","r",stdin);
  freopen("semne.out","w",stdout);         
  
  lint i,n,S=0, A=0,B=0;
  
  srand((lint)time(0));
  
          
  scanf("%d%d", &n,&S);
  
  for(i=1;i<=n;++i)
   {
    scanf("%d", v+i);
    if(A - B <= S)
     {
      a[++a[0]] = i;
      A += v[i];
      s[i] = '+';
      } 
      else
     {
      b[++b[0]] = i;
      B += v[i];
      s[i] = '-';
     } 
   }  

  while(A-B != S)
   { 
    if(A-B > S) 
     {
      // mut din A in B     
      int tmp = (rand()%a[0])+1; 
      b[++b[0]] = a[tmp];
      A -= v[a[tmp]];     
      B += v[a[tmp]];
      s[a[tmp]] = '-';      
      a[tmp] = a[a[0]--];            
     }
    if(A-B < S)
     {
      // mut din B in A     
      int tmp = (rand()%b[0])+1; 
      a[++a[0]] = b[tmp];
      A += v[b[tmp]];     
      B -= v[b[tmp]];
      s[b[tmp]] = '+';
      b[tmp] = b[b[0]--];            
     }    
     
    if(b[0] == 0 && A-B != S) 
     {
      // mut din A in B     
      int tmp = (rand()%a[0])+1; 
      b[++b[0]] = a[tmp];
      A -= v[a[tmp]];     
      B += v[a[tmp]];
      s[a[tmp]] = '-';      
      a[tmp] = a[a[0]--];            
     }
     
    if(a[0] == 0 && A-B != S) 
     {
      // mut din B in A     
      int tmp = (rand()%b[0])+1; 
      a[++a[0]] = b[tmp];
      A += v[b[tmp]];     
      B -= v[b[tmp]];
      s[b[tmp]] = '+';
      b[tmp] = b[b[0]--];            
     }        
   }
   
  for(i=1;i<=n;++i)
   printf("%c", s[i]);
     

  return 0;         
 }