글 읽기 - C++로 했는데 왜 틀린지 모르겠습니다.

a1clsrotorl 3년 전 0

힙정렬을 이용했는데, 힙정렬을 할 때 x값이 같다면 y값이 큰 것도 바꿔주는 방식으로 해보려고 했습니다.

문제에 있는 예제는 물론이고, 질문 게시판의 반례들도 다 해봤을 때 안되는 것이 없는데 틀렸다고 합니다.

뭐가 문제인지 알려주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, x, y;
	cin >> n;
	int **arr;
	arr = new int* [n];
	for (int i = 0; i < n; i++)
	{
		arr[i] = new int[2];
	}
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		arr[i][0] = x;
		arr[i][1] = y;
	}
	//heapify
	for (int i = 1; i < n; i++)
	{
		int c = i;
		do {
			int root = (c - 1) / 2;
			if (arr[root][0] < arr[c][0])
			{
				int tmp = arr[root][0];
				int temp = arr[root][1];
				arr[root][0] = arr[c][0];
				arr[root][1] = arr[c][1];
				arr[c][0] = tmp;
				arr[c][1] = temp;
			}
			if (arr[root][0] == arr[c][0] && arr[root][1] < arr[c][1])
			{
				int tmp = arr[root][0];
				int temp = arr[root][1];
				arr[root][0] = arr[c][0];
				arr[root][1] = arr[c][1];
				arr[c][0] = tmp;
				arr[c][1] = temp;
			}
			c = root;
		} while (c != 0);
	}
	//정렬
	for (int i = n-1; i >= 0; i--)
	{
		int tmp = arr[0][0];
		int temp = arr[0][1];
		arr[0][0] = arr[i][0];
		arr[0][1] = arr[i][1];
		arr[i][0] = tmp;
		arr[i][1] = temp;
		int c = 1;
		int root = 0;
		do {
			c = 2 * root + 1;
			if (c < i - 1 && arr[c][0] < arr[c + 1][0])
			{
				c += 1;
			}
			if (c < i && arr[root][0] < arr[c][0])
			{
				tmp = arr[root][0];
				temp = arr[root][1];
				arr[root][0] = arr[c][0];
				arr[root][1] = arr[c][1];
				arr[c][0] = tmp;
				arr[c][1] = temp;
			}
			if (c < i && arr[root][0] == arr[c][0] && arr[root][1] < arr[c][1])
			{
				tmp = arr[root][0];
				arr[root][0] = arr[c][0];
				arr[c][0] = tmp;
				temp = arr[root][1];
				arr[root][1] = arr[c][1];
				arr[c][1] = temp;
			}
			root = c;
		} while (c < i);
	}
	for (int i = 0; i < n; i++)
	{
		cout << arr[i][0] << " " << arr[i][1] << "\n";
	}
}

tnghkswkd123 2년 전 0

62 ~ 65번째 줄에 x 값이 같고 y같이 차이가 나는 경우에도 c값을 증가시켜주는 걸 추가해주셔야 할거같아요

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

문제

문제

출처

ICPC

C++로 했는데 왜 틀린지 모르겠습니다.

a1clsrotorl 3년 전 0

tnghkswkd123 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말