글 읽기 - InsufficientSpace 에러?

themion 2년 전 0

본 적 없는 에러가 발생해 질문드립니다.

메모리 제한을 벗어나거나 인덱스 범위를 벗어난 것 같지는 않은데, 왜 이런 문제가 발생하는 걸까요?

#include <iostream>

using namespace std;

#define MAX_N 100000

// int를 절댓값과 부호로 나누어 저장
class num {
public:
    // 실제 값이 음수라면 true
    bool b = false;
    // 실제 값의 절댓값
    int i = 0;

    num() {}
    num(int i_) { b = i_ < 0; i = abs(i_); }
    // x의 절댓값
    int abs(int x) { return x < 0 ? -x : x; }
    // 클래스의 실제 값
    int val() { return b ? -i : i; }
};

// 두 num 클래스를 비교
bool operator<(num p, num q) { return p.i == q.i ? p.b : p.i < q.i; }
bool operator>(num p, num q) { return p.i == q.i ? !p.b : p.i > q.i; }
// num 클래스 p의 실제 값을 q와 비교
bool operator==(num p, int q) { return q == p.val(); }

template <typename T>
class max_heap {
private:
    // 힙의 크기
    int len;
    // heap: 최소 힙
    T heap[MAX_N];

    void swap(T &a, T &b) { T temp = a; a = b; b = temp; }
    // i의 부모 노드의 인덱스
    int prev(int i) { return (i - 1) / 2; }
    // i의 두 자식 노드 중 더 큰 노드의 인덱스
    int next(int i) {
        if (heap[2 * i + 2] == 0) return 2 * i + 1;
        return 2 * i + (heap[2 * i + 1] < heap[2 * i + 2] ? 1 : 2); 
    }

public:
    // x를 heap에 push
    void push(T x) {
        // x를 저장할 인덱스
        int i = len++;
        // 힙의 마지막에 x를 push한 뒤
        heap[i] = x;
        // 부모 노드가 자신보다 클 때까지 부모 노드와 현재 노드를 swap
        for (int j = prev(i); i && heap[i] < heap[j]; i = j, j = prev(i))
            swap(heap[i], heap[j]);
    }

    T pop() {
        // heap의 노드를 swap하기 위한 인덱스
        int i = 0;
        // pop한 노드의 값
        T ret = heap[i];

        // 루트 노드와 마지막 노드를 swap한 뒤 마지막 노드를 0으로 설정해 pop
        swap(heap[i], heap[len ? --len : len]);
        heap[len] = T();

        // 자식 노드가 자신보다 작을 때까지
        // 자식 노드 중 더 큰 노드와 현재 노드를 swap
        for (int j = next(i); j < len && heap[i] > heap[j]; i = j, j = next(i))
            swap(heap[i], heap[j]);

        return ret;
    }
};

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // N: 연산의 개수, x: 각 연산
    int N, x;
    max_heap<num> h;

    // 각 연산에 대해
    for (cin >> N; N--; ) {
        // 연산을 입력받은 뒤
        cin >> x;

        // x가 0이 아니라면 해당 수를 힙에 push
        if (x != 0) h.push(num(x));
        // 아니라면 힙에서 노드를 하나 pop한 뒤 출력
        else cout << h.pop().val() << '\n';
    }

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

InsufficientSpace 에러?

themion 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말