Cod sursa(job #405874)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 28 februarie 2010 20:50:11
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
# include <cstdio>
# include <time.h>
# include <stdlib.h>

using namespace std;

# define FIN "semne.in"
# define FOUT "semne.out"
# define MAX_N 50005

int a[MAX_N];
int semn[MAX_N];
int ind[2][MAX_N];
long long S, Psum;
int N, i, val, rnd;

    int main()
    {
        freopen(FIN, "r", stdin);
        freopen(FOUT, "w", stdout);
        
        srand(time(NULL));
        
        scanf("%d%lld", &N, &S);
        
        for (i = 1; i <= N; ++i)
        {
            scanf("%d", &a[i]);
            
            semn[i] = rand() % 2;
            ind[semn[i]][++ind[semn[i]][0]] = i;
            semn[i] ? Psum += (long long) a[i] : Psum -= (long long) a[i];
        }
        
        while (S != Psum)
        {
             if (Psum < S)
             {
                  rnd = rand() % ind[0][0] + 1;

                  Psum += (long long) (a[ind[0][rnd]] << 1);
                  semn[ind[0][rnd]] = 1;
                  ind[1][++ind[1][0]] = ind[0][rnd];
                  ind[0][rnd] = ind[0][ind[0][0]--];
             } else
             {
                  rnd = rand() % ind[1][0] + 1;

                  Psum -= (long long) (a[ind[1][rnd]] << 1);
                  semn[ind[1][rnd]] = 0;
                  ind[0][++ind[0][0]] = ind[1][rnd];
                  ind[1][rnd] = ind[1][ind[1][0]--];
                   
             }
        }
        
        for (i = 1; i <= N; ++i)
           semn[i] == 1 ? printf("+") : printf("-");
        
        return 0;
    }