글 읽기 - 반례가 궁금합니다

kim6394 3년 전 0

min 힙을 직접 구현했습니다.

먼저 들어온 순서를 idx로 저장하여 age가 같을때 idx가 작은 순으로 pop하도록 구현했는데요.

4% 진행 중 틀렸다고 나오는데, 혹시 어떤 반례 때문에 동작하지 않는지 궁금합니다.

#include <stdio.h>

#define MAXN 100000
#define MAXNAME 100

int N, age;
char name[MAXNAME + 1];

struct HEAP {
	int age;
	int idx;
	char name[MAXNAME + 1];
}heap[MAXN + 1];
int heap_size;

void push(HEAP h) {
	int target = heap_size + 1;
	while (target != 1 && (heap[target / 2].age > h.age || (heap[target / 2].age == h.age && heap[target / 2].idx > h.idx))) {
		heap[target] = heap[target / 2];
		target /= 2;
	}
	heap[target] = h;
	++heap_size;
}

HEAP pop() {
	int parent = 1, child = 2;
	HEAP p = heap[parent];
	HEAP temp = heap[heap_size];

	while (child < heap_size) {
		while (child + 1 < heap_size && (heap[child].age > heap[child + 1].age || (heap[child].age == heap[child + 1].age && heap[child].idx > heap[child + 1].idx))) {
			++child;
		}
		if (temp.age < heap[child].age || (temp.age == heap[child].age && temp.idx <= heap[child].idx)) break;

		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}

	heap[parent] = temp;
	--heap_size;

	return p;
}

void strcopy(char *a, char *b) {
	while ((*a++ = *b++));
}

int main(void)
{
	scanf("%d", &N);

	heap_size = 0;

	int i;
	HEAP p;
	for (i = 1; i <= N; ++i) {
		scanf("%d %s", &age, name);
		p.age = age;
		p.idx = i;
		strcopy(p.name, name);
		push(p);
	}

	for (i = 1; i <= N; ++i) {
		p = pop();
		printf("%d %s\n", p.age, p.name);
	}

	return 0;
}

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

문제

문제

출처

ICPC

반례가 궁금합니다

kim6394 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말