글 읽기 - 반례를 찾지 못하겠습니다. 도와주세요

shfshfdl 2년 전 1

우선 생각한 알고리즘은 키와 몸무게의 합이 크면

그만큼 덩치가 크다는 접근으로 정렬을 하였습니다.

그 후 정렬 값에서 키와 몸무게가 모두 클 경우에만 랭크를 올려주는 식으로

해서 만들어본 샘플예제들은 통과를 하는데

반례를 찾지 못하겠습니다.

도와주세요

감사합니다.

#include "stdio.h"
#define swap(a, b) {int temp=(a);(a)=(b);(b)=temp;}

int inputData[50][3]; // 0 : x, 1 : y, 2 : answer
int sortData[50][3]; // 0 : x, 1 : y, 2 : inputData의 index

int partition(int l, int r) {
	int pivot = l;
	int i = l;
	int j = r;

	while (i <= j) {
		while (sortData[i][0] + sortData[i][1] <= sortData[pivot][0] + sortData[pivot][1]) if (++i >= r) break;
		while (sortData[j][0] + sortData[j][1] >= sortData[pivot][0] + sortData[pivot][1]) if (--j <= l) break;

		if (i < j) {
			swap(sortData[i][0], sortData[j][0]);
			swap(sortData[i][1], sortData[j][1]);
			swap(sortData[i][2], sortData[j][2]);
		}
	}

	swap(sortData[pivot][0], sortData[j][0]);
	swap(sortData[pivot][1], sortData[j][1]);
	swap(sortData[pivot][2], sortData[j][2]);

	return j;
}

void qsort(int l, int r) {
	if (l < r) {
		int pivot = partition(l, r);
		qsort(l, pivot - 1);
		qsort(pivot + 1, r);
	}
}

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

	int i = 0;
	while (i<n) {
		scanf("%d %d", &inputData[i][0], &inputData[i][1]);
		sortData[i][0] = inputData[i][0];
		sortData[i][1] = inputData[i][1];
		sortData[i][2] = i;

		i++;
	}
	qsort(0, n - 1);

	int answer = 1;
	int corr = 0;
	inputData[sortData[n - 1][2]][2] = answer;

	for (int i = n-2; i >= 0; i--) {
		if (sortData[i + 1][0] > sortData[i][0] && sortData[i + 1][1] > sortData[i][1]) {
			inputData[sortData[i][2]][2] = ++answer + corr;
			corr = 0;
		} else {
			inputData[sortData[i][2]][2] = answer;
			corr++;
		}
	}

	for (int i = 0; i < n; i++) {
		printf("%d", inputData[i][2]);
		(i != n - 1)?printf(" "):puts("");
	}

	return 0;
}

shfshfdl 2년 전 0

제 반례는 아래와 같아요 rank 측정쪽에 오류가있었네요

100 2

56 43

55 42

2 1

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

문제

문제

출처

ACM-ICPC

반례를 찾지 못하겠습니다. 도와주세요

shfshfdl 2년 전 1

shfshfdl 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말