글 읽기 - [최대 힙] 반례 혹은 오류 지적 부탁드립니다.

rkdwldnjs9128 1년 전 0

해당 게시판의 반례값 및

구글링해서 나오는 반례값들을 전부 모아 테스트해보았는데, 전부 정상적으로 나왔습니다.

어느 부분에서 문제가 있는지 궁금합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int map[100001] = { 0, };
int i = 0;

void push_s(const int inp)
{
    i++;
    int a = i;
    map[i] = inp;

    int temp = 0;
    int check = true;
    while (a > 1) {
        switch (a % 2)
        {
        case 0:
            if (map[a / 2] < map[a])
            {
                temp = map[a];
                map[a] = map[a / 2];
                map[a / 2] = temp;
                a /= 2;
            }
            else check = false;
            break;
        case 1:
            if (map[(a - 1) / 2] < map[a])
            {
                temp = map[a];
                map[a] = map[(a - 1) / 2];
                map[(a - 1) / 2] = temp;
                a = (a - 1) / 2;
            }
            else check = false;
            break;
        }
        if (check == false)break;
    }
    return;
}
void pop_max()
{
    if (i == 0)
    {
        printf("0\n");
        return;
    }
    printf("%d\n", map[1]);
    int a = 1;
    map[1] = map[i];
    int temp = 0;
    map[i] = 0;
    i--;

    while (true)
    {
        if (i == 1 || i == 0) break;
        if (i > a * 2 + 1)
        {
            if (map[2 * a] > map[2 * a + 1])
            {
                if (map[2 * a] > map[a])
                {
                    temp = map[a];
                    map[a] = map[2 * a];
                    map[2 * a] = temp;
                    a *= 2;
                }
                else break;
            }
            else
            {
                if (map[2 * a + 1] > map[a])
                {
                    temp = map[a];
                    map[a] = map[2 * a + 1];
                    map[2 * a + 1] = temp;
                    a = a * 2 + 1;
                }
                else break;
            }
        }
        else
        {
            if (map[2 * a] > map[a])
            {
                temp = map[a];
                map[a] = map[2 * a];
                map[2 * a] = temp;
                a *= 2;
            }
            else break;
        }
        if (a >= i) break;
    }

}

int main()
{

    int n = 0;
    scanf("%d", &n);
    int temp = 0;
    int test = false;

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &temp);
        if (temp == 0)
        {
            pop_max();
        }
        else
        {
            push_s(temp);
        }

    }



}

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

문제

문제

출처

ICPC

[최대 힙] 반례 혹은 오류 지적 부탁드립니다.

rkdwldnjs9128 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말