Cod sursa(job #50944)

Utilizator raula_sanChis Raoul raula_san Data 9 aprilie 2007 14:16:51
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>

#define dim 50001

long long A[dim];
long long S, Sum;

long N, step;

char Sol[dim];

void get_data();
void preprocess();
void solve();
void print();

long b_search(long long);

int main()
{
    get_data();
    preprocess();
    solve();
    print();
    
    return 0;
}

void get_data()
{
     freopen("semne.in", "r", stdin);
     
     long i;
     for(scanf("%ld %lld", &N, &S), i=1; i<=N; ++i)
     {
                      scanf("%lld", A+i);
                      Sum += A[i];
                      Sol[i-1] = '+';
     }
     
     fclose(stdin);
}

void preprocess()
{
     for(step=1; step<=N; step<<=1);
}

void solve()
{
     long long value;
     long p;
     
     while(Sum != S)
     {
               if(Sum > S)
               {
                      value = Sum - S;
                      p = b_search(value);
                      Sol[p-1] = '-';
                      Sum -= A[p];
               }
               else
               {
                   value = S - Sum;
                   p = b_search(value);
                   Sol[p-1] = '+';
                   Sum += A[p];
               }
     }
}

void print()
{
     freopen("semne.out", "w", stdout);
     
     puts(Sol);
     
     fclose(stdout);
}

long b_search(long long value)
{
     long i, Step;
     for(i=1, Step=step; Step; Step>>=1)
              if(i+Step <= N && value <= A[i+Step])
                        i += Step;
     return i;
}