Cod sursa(job #1538724)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 noiembrie 2015 17:53:00
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <stdlib.h>
#include <time.h>
#include <algorithm>

#define DIM 52000
#define cost first
#define position second
using namespace std;

int Freq[DIM], N, K1, K2, X;
pair <int, int> Stack1[DIM], Stack2[DIM];
long long S, T;

void pushStack1 (pair <int, int> value) {
    Stack1[K1++] = value;
    return;
}

void pushStack2 (pair <int, int> value) {
    Stack2[K2++] = value;
    return;
}

void popStack1 (int pos) {
    swap (Stack1[pos], Stack1[K1-1]); K1 --;
    return;
}

void popStack2 (int pos) {
    swap (Stack2[pos], Stack2[K2-1]); K2 --;
    return;
}

int main () {

    freopen ("semne.in", "r", stdin );
    freopen ("semne.out","w", stdout);

    srand (time(0));

    scanf ("%d %lld", &N, &T);
    for (int i = 1; i <= N; i ++) {
        scanf ("%d", &X);

        if (S <= T) {
            pushStack1 (make_pair(i, X));
            S += X;
        } else {
            pushStack2 (make_pair(i, X));
            S -= X;
        }
    }

    while (S != T) {
        if (S > T) {
            int pos = rand() % K1;
            pair <int, int> value = Stack1[pos];
            S -= value.cost * 2;

            popStack1 (pos);
            pushStack2(value);
        } else {
            int pos = rand() % K2;
            pair <int, int> value = Stack2[pos];
            S += value.cost * 2;

            popStack2 (pos);
            pushStack1(value);
        }
    }

    for (int i = 0; i < K1; i ++)
        Freq[Stack1[i].position] = 1;

    for (int i = 1; i <= N; i ++)
        printf ("%c", (Freq[i] == 1) ? '+' : '-');

    return 0;
}