Cod sursa(job #50910)

Utilizator crawlerPuni Andrei Paul crawler Data 9 aprilie 2007 13:13:15
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <time.h>

#define Nmax 50002
#define key 1234566691

typedef long long lint;

int a[Nmax], b[Nmax], v[Nmax];
char s[Nmax];

#define Dim 10000 

char buf[Dim];
int poz = 0;

void cit(int &x)
{
     x=0;
     while (buf[poz]<'0'){
           poz++;
           if (poz==Dim) fread(buf, 1, Dim, stdin), poz=0;
     }
     while (buf[poz]>='0'){
           x=x*10+buf[poz++]-'0';
           if (poz==Dim) fread(buf, 1, Dim, stdin), poz=0;
     }
}

int MOD = (1<<31)-1;
#define mod &= MOD
int r, p;

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

inline int rand()
 {
  r+=key;
  r mod;
  return r;         
 }

int main()
 {
  freopen("semne.in","r",stdin);
  freopen("semne.out","w",stdout);         
  
  int i,n;
  lint A=0,B=0,S;
  
 // srand((int)time(0));
  srand(666);  
          
  scanf("%d%lld", &n,&S);
  
  for(i=0;i<n;++i)
   {
    cit(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]--];            
     }          
   }

  s[n] = '\n';
  fputs(s,stdout);

  return 0;         
 }