글 읽기 - 8979 올림픽 질문드립니다.

skynet0149 5년 전 0

안녕하세요 테스트케이스를 10개정도 만들어서 돌려보았는데 틀린부분을 알 수 없어 제가 한 접근 방법이 잘못되었는지 질문드립니다.

heap을 통하여 정렬을하는데 정렬하는 함수로는 gt함수를 사용
gt 함수는 금(g), 은(s), 동(c) 을 비교하여 bool 함수로 compare사용
idx 변수를 통하여 등수를 출력합니다.
cnt는 이전의 금, 은, 동 과 현재가 같은경우 같은게 몇개 있는지 cnt++를 해줍니다.
만약 다를 경우는 idx+=cnt를 해줍니다.
해당하는 국가가 나올경우 출력해줍니다.

#include <iostream>
#include <cstdio>
using namespace std;
struct Country {
	int g, s, c, num;
	Country() { g = s = c = num = 0; }
	Country(int g, int s, int c, int num) {
		this->g = g; this->s = s; this->c = c; this->num = num;
	}
};
template<class T>
struct HEAP {
	T *arr;
	int hsize;
	bool(*cmptype)(const T &a, const T &b);

	HEAP(int size, bool(*cmpfunc)(const T &a, const T &b)) {
		arr = new T[size];
		hsize = 0;
		cmptype = cmpfunc;
	}

	void push(T &a) {
		arr[++hsize] = a;
		upheap();
	}
	void upheap() {
		int cur = hsize;
		while (cur / 2 >= 1 && gt(arr[cur], arr[cur/2])) {
			swap(arr[cur], arr[cur / 2]);
			cur /= 2;
		}
	}
	void pop() {
		if (hsize == 0)
			return;
		arr[1] = arr[hsize--];
		downheap();
	}
	void downheap() {
		int cur = 1;
		while (cur * 2 <= hsize) {
			int target = cur * 2;
			if (target + 1 <= hsize && cmptype(arr[target + 1], arr[target]))
				swap(arr[target], arr[target + 1]);
			if (cmptype(arr[target], arr[cur])) {
				swap(arr[target], arr[cur]);
				cur = target;
			}
			else break;
		}
	}
	T& top() {
		return arr[1];
	}
	int size() {
		return hsize;
	}
	void swap(T &a, T &b) { T t = a; a = b; b = t; }
};
template<class T>
bool gt(T &a, T &b) {
	if (a.g > b.g)
		return true;
	else if (a.g == b.g) {
		if (a.s > b.s)
			return true;
		else if (a.s == b.s) {
			if (a.c > b.c)
				return true;
		}
	}
	return false;
}
int main() {
	int K;
	int n;
	int a, b, c, d;
	scanf("%d %d", &n, &K);
	HEAP<Country> heap(2002, gt);
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		Country C(b, c, d, a);
		heap.push(C);
	}

	int idx;        //등수
	int hSize = heap.size();
    // 이전 값과 현재값을 비교하기 위하여 이전 값들을 금, 은, 동 순서로 저장
	int preg=0, pres=0, prec=0;
	int cnt;
	//heap 정렬 잘 되는지 검사
	//for (int i = 0; i < hSize; i++) {
	//	printf("%d %d %d %d\n", heap.top().num, heap.top().g, heap.top().s, heap.top().c);
	//	heap.pop();
	//}
	for (int i = 0; i < hSize; i++) {
		if (i == 0) {
			idx = cnt = 1;
			preg = heap.top().g;
			pres = heap.top().s;
			prec = heap.top().c;
		}
		else {
			if (preg != heap.top().g || pres != heap.top().s || prec != heap.top().c){
				idx += cnt;
				cnt = 1;
			}
			else
				cnt++;
			preg = heap.top().g;
			pres = heap.top().s;
			prec = heap.top().c;
		}
		if (K == heap.top().num)
			return !printf("%d\n", idx);
		// 순위 동작 여부 검사
		//printf("%d %d %d %d %d\n", heap.top().num, heap.top().g, heap.top().s, heap.top().c, idx);
		heap.pop();
	}
	return 0;
}

djm03178 5년 전 4

코드가 꽤 복잡해서 분석해드리기는 어렵지만, 랜덤 반례들을 대신 몇 개 드립니다.

매우 작은 케이스들에서는 잘 안 나오네요.

10
0 0 1
1 2 1
2 1 1
0 1 2
0 2 1
2 2 1
2 2 0
1 1 2
1 2 0
2 0 0
output: 6
correct answer: 5

5
0 1 0
1 1 1
2 2 1
2 0 0
1 0 0
1 0 2
0 0 1
0 1 0
0 1 2
output: 5
correct answer: 4

7
2 2 1
0 1 2
0 1 2
1 0 1
0 2 1
1 2 0
1 2 1
1 1 2
0 2 2
1 0 1
output: 6
correct answer: 5

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

문제

문제

출처

ICPC

8979 올림픽 질문드립니다.

skynet0149 5년 전 0

djm03178 5년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말