Cod sursa(job #49856)

Utilizator cos_minBondane Cosmin cos_min Data 6 aprilie 2007 15:04:24
Problema Semne Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <stdio.h>
#include <fstream>
#include <stdlib.h>
#include <time.h>
using namespace std;

#define in "semne.in"
#define out "semne.out"
#define dim 50001

unsigned long long a[dim];
unsigned long long stotal=0, stotal2=0;
char v[dim];
int n, s;
bool sel[dim];

int main()
{
    srand(time(0)%666730);
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    int gasit=0;
    
    scanf("%d%d",&n,&s);
    
    for ( int i = 1; i <= n; i++ ) scanf("%llu",&a[i]), stotal += a[i], v[i-1] = '+';
    
    a[0] = 0;
    //a[n] = 0;
    
    long long splus=0;
    long long rest=0;
    long long sminus=0;
    int minus=0;
    
    int p=0;

    if ( s < 0 ) s *= -1, minus = 1;
    
    while ( !gasit )
    {
          //for (int i = 1; i <= n; i++ ) sel[i] = 0;
          memset(sel,0,sizeof(sel[0])*(n+1));
           
          stotal2 = stotal;
          splus = 0;
          sminus = stotal;
          int j;
          int t=0;
          int ok =0;
          
          if ( sminus == s ) 
          {
              gasit = 1;
              for (int i = 1; i <= n; i++ ) sel[i] = 1;
              p = 0;
              ok = 1;
          }
          
          while ( ok == 0 )
          {
                j = rand()%(n);
                if ( j == 0 || sel[j] ) continue; 
                
                if ( !sel[j] ) splus += a[j], sel[j] = 1, t++, sminus -= a[j];
                
                if ( abs(sminus - splus) == s ) 
                {
                     gasit = 1, ok = 1;
                     
                     if ( minus == 0 )
                     {
                        if ( sminus > splus ) p = 1;
                        else                  p = 0;
                     }
                     if ( minus == 1 )
                     {
                        if ( sminus > splus ) p = 0;
                        else                  p = 1;
                     }
                }
                
                if ( splus - sminus > s || t == n ) ok = 1;
          }
    }
    
    for ( int i = 0; i < n; i++ )
    {
        if ( sel[i+1] == p ) v[i] = '-';
        else            v[i] = '+';
    }
    
    for ( int i = 0; i < n; i++ )
        printf("%c",v[i]);
    //printf("%d ", p);
}