글 읽기 - 어디가 틀렸나요?

pos10022 7년 전 0

다른 데이터들을 넣었는데 제대로 나왔어요.

그런데 틀렸다고 나오네요.

그리고 힙정렬로 했습니다.

#include <stdio.h>

int n,x[100005],y[100005],heap[100005][2];
int ans[100005][2];

int main()
{
	int i,j,m,tmp;

	scanf("%d",&n);

	for(i=1;i<=n;i++) {
		scanf("%d %d",&x[i],&y[i]);
	}

	for(i=1;i<=n;i++) {
		heap[i][0]=x[i]; heap[i][1]=y[i]; 
		for(j=i;j>=2;j/=2) {
			if(heap[j][0]<heap[j/2][0]) {
				tmp=heap[j][0]; heap[j][0]=heap[j/2][0]; heap[j/2][0]=tmp; 
				tmp=heap[j][1]; heap[j][1]=heap[j/2][1]; heap[j/2][1]=tmp; 
			}
			else if(heap[j][0]==heap[j/2][0]) {
				if(heap[j][1]<heap[j/2][1]) {
					tmp=heap[j][0]; heap[j][0]=heap[j/2][0]; heap[j/2][0]=tmp; 
					tmp=heap[j][1]; heap[j][1]=heap[j/2][1]; heap[j/2][1]=tmp; 
				}
			}
		}
	}

	ans[1][0]=heap[1][0]; ans[1][1]=heap[1][1];
	heap[1][0]=heap[n][0]; heap[1][1]=heap[n][1];
	heap[n][0]=0; heap[n][1]=0;
	m=n-1;

	for(i=2;i<=n;i++) {
		j=1;
		while(1) {
			if(j*2>m) break;

			if(heap[j][0]>heap[j*2][0] && (j*2==m || heap[j*2][0]<heap[j*2+1][0])) {
				tmp=heap[j][0]; heap[j][0]=heap[j*2][0]; heap[j*2][0]=tmp;
				tmp=heap[j][1]; heap[j][1]=heap[j*2][1]; heap[j*2][1]=tmp;
				j*=2;
			}
			else if(heap[j][0]>heap[j*2+1][0] && heap[j*2][0]>heap[j*2+1][0] && j*2+1<=m) {
				tmp=heap[j][0]; heap[j][0]=heap[j*2+1][0]; heap[j*2+1][0]=tmp;
				tmp=heap[j][1]; heap[j][1]=heap[j*2+1][1]; heap[j*2+1][1]=tmp;
				j*=2; j++;
			}
			else if(heap[j][0]==heap[j*2][0] && heap[j][0]==heap[j*2+1][0]) {
				if(heap[j][1]>heap[j*2][1] && (j*2==m || heap[j*2][1]<heap[j*2+1][1])) {
					tmp=heap[j][0]; heap[j][0]=heap[j*2][0]; heap[j*2][0]=tmp;
					tmp=heap[j][1]; heap[j][1]=heap[j*2][1]; heap[j*2][1]=tmp;
					j*=2;
				}
				else if(heap[j][1]>heap[j*2+1][1] && heap[j*2][1]>heap[j*2+1][1] && j*2+1<=m) {
					tmp=heap[j][0]; heap[j][0]=heap[j*2+1][0]; heap[j*2+1][0]=tmp;
					tmp=heap[j][1]; heap[j][1]=heap[j*2+1][1]; heap[j*2+1][1]=tmp;
					j*=2; j++;
				}
				else break;
			}
			else if(heap[j][0]==heap[j*2][0]) {
				if(heap[j][1]>heap[j*2][1] && (j*2==m || heap[j*2][1]<heap[j*2+1][1])) {
					tmp=heap[j][0]; heap[j][0]=heap[j*2][0]; heap[j*2][0]=tmp;
					tmp=heap[j][1]; heap[j][1]=heap[j*2][1]; heap[j*2][1]=tmp;
					j*=2;
				}
				else break;
			}
			else if(heap[j][0]==heap[j*2+1][0]) {
				if(heap[j][1]>heap[j*2+1][1] && heap[j*2][1]>heap[j*2+1][1] && j*2+1<=m) {
					tmp=heap[j][0]; heap[j][0]=heap[j*2+1][0]; heap[j*2+1][0]=tmp;
					tmp=heap[j][1]; heap[j][1]=heap[j*2+1][1]; heap[j*2+1][1]=tmp;
					j*=2; j++;
				}
				else break;
			}
			else break;
		}
		ans[i][0]=heap[1][0]; ans[i][1]=heap[1][1];
		heap[1][0]=heap[m][0]; heap[1][1]=heap[m][1];
		heap[m][0]=heap[m][1]=0;
		m--;
	}

	for(i=1;i<=n;i++) {
		printf("%d %d\n",ans[i][0],ans[i][1]);
	}
}

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

문제

문제

출처

ICPC

어디가 틀렸나요?

pos10022 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말