글 읽기 - 반례가 있을까요..?

kfc 4년 전 0

이상하게 정올에서 채점했을 때는 맞았다고 뜨는데 여기서는 89%에서 계속 틀리네요...

혹시 반례 찾아주시면 감사하겠습니다.!!

#include <stdio.h>

int N, M;

typedef struct point
{
	int num,u, v;
}Point;

Point bus[1000005];
int check[500005];
Point sort[500005];

void merge(int left, int mid, int right)
{
	int i, j, k, l;

	i = left;j = mid + 1;k = left;

	while (i <= mid && j <= right)
	{
		if (bus[i].u < bus[j].u)
		{
			sort[k].u = bus[i].u;sort[k].v = bus[i].v;sort[k].num = bus[i].num;k++;i++;
		}
		else if (bus[i].u > bus[j].u)
		{
			sort[k].u = bus[j].u;sort[k].v = bus[j].v;sort[k].num = bus[j].num;k++;j++;
		}
		else
		{
			if (bus[i].v > bus[j].v)
			{
				sort[k].u = bus[i].u;sort[k].v = bus[i].v;sort[k].num = bus[i].num;
				k++;i++;
			}
			else
			{
				sort[k].u = bus[j].u;sort[k].v = bus[j].v;sort[k].num = bus[j].num;
				k++;j++;
			}
		}
	}

	if (i > mid)
	{
		for (l = j;l <= right;l++)
		{
			sort[k].u = bus[l].u;sort[k].v = bus[l].v;sort[k].num = bus[l].num;
			k++;
		}
	}
	else
	{
		for (l = i;l <= mid;l++)
		{
			sort[k].u = bus[l].u;sort[k].v = bus[l].v;sort[k].num = bus[l].num;
			k++;
		}
	}

	for (l = left;l <= right;l++)
	{
		bus[l].u = sort[l].u;bus[l].v = sort[l].v;bus[l].num = sort[l].num;
	}
}

void merge_sort(int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		merge_sort(left, mid);
		merge_sort(mid + 1, right);
		merge(left, mid, right);
	}
}

int comp(int i, int j)
{
	//printf("시작 %d %d\n", i, j);
	//printf("%d %d\n", bus[i].u, bus[i].v);
	//printf("%d %d\n", bus[j].u, bus[j].v);
	if (bus[i].u < bus[i].v)
	{
		if (bus[j].u < bus[j].v)
		{
			if (bus[j].u >= bus[i].u&&bus[j].v <= bus[i].v)
				return 1;
		}
	}
	else
	{
		if (bus[j].u < bus[j].v)
		{
			if (bus[j].u >= bus[i].u&&bus[j].v >= bus[i].v)return 1;
			else if (bus[j].u <= bus[i].u&&bus[j].v <= bus[i].v) return 1;
		}
		else
		{
			if (bus[j].u >= bus[i].u&&bus[j].v <= bus[i].v)return 1;
		}
	}

	return 0;
}

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

	scanf("%d", &M);

	for (int i = 1;i <= M;i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);

		bus[i].num = i;
		bus[i].u = a;bus[i].v = b;
	}

	merge_sort(1, M);

	for (int i = 1;i <= M;i++)
	{
		bus[i + M].u = bus[i].u;
		bus[i + M].v = bus[i].v;
		bus[i + M].num = bus[i].num;
	}


	for (int i = 1;i <= M;i++)
	{
		if (check[bus[i].num] == 1)continue;
		int j;
		j = i + 1;
		while (comp(i, j) && bus[i].num != bus[j].num)
		{
			check[bus[j].num] = 1;
			j++;
		}
		i = j - 1;
	}

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

	return 0;

}

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

문제

문제

출처

ICPC

반례가 있을까요..?

kfc 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말