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

gginn1234 3년 전 1

1966번 테스트케이스는 모두 맞았는데요..

정작 결과는 "틀렸습니다" 라고 명확하게 나오네요..

제가 틀린 것은 99.9% 확실할 것 같으니,,

혹시 반례가 있으시면, 가르쳐 주시면 감사하겠습니다 ㅠㅠ

(샘플데이터랑 테스트데이터 100개는 모두 맞아요.. ㅠ)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int k;

typedef struct {
	int cnt;
	int* prior;
	int* Q;
	int front, rear;
}QType;

QType* createQ(int k)
{
	QType* L = malloc(sizeof(QType));
	L->cnt = 0;
	L->front = L->rear = 0;
	L->Q = malloc(sizeof(int) * (k));
	L->prior = malloc(sizeof(int) * (k));
	return L;
}

void enQueue(QType* L, int pr, int index)
{
	L->cnt++;
	L->Q[L->rear] = L->prior[L->rear] = pr;
	L->rear = (L->rear + 1) % k;
}

int deQueue(QType* L, int index)
{
	L->cnt--;
	int item = L->Q[index];
	L->Q[index] = 0;
	return item;
}

int Round(QType* L, int index)
{
	int i, order = 0;
	for (i = 0; i != index || L->prior[order] != L->Q[i]; i = (i + 1) % k) {
		if (L->Q[i] == 0)	continue;
		if (L->Q[i] == L->prior[order]) {
			deQueue(L, i);
			order++;
		}
	}
	return order + 1;
}

void compare(const void* a, const void* b)
{
	int n1 = *(int*)a, n2 = *(int*)b;
	if (n1 < n2)
		return 1;
	else if (n1 > n2)
		return -1;
	return 0;
}

int main()
{
	int n, i, index, j, pr;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d %d", &k, &index);
		QType* L = createQ(k);
		for (j = 0; j < k; j++) {
			scanf("%d", &pr);
			enQueue(L, pr, j);
		}
		qsort(L->prior, k, sizeof(int), compare);

		printf("%d\n", Round(L, index));
		free(L);
	}
	return 0;
}

gginn1234 3년 전 0

printerqueue.in

printerqueue.out

테스트케이스 100개와 그 결과파일입니다.

게시판을 보니, 반례요청하시는 분들이 많으셔서;;

(물론 저도 반례를 더 찾고 있지만요;;)

(위의 TC부터 체크해보세요~ 게시판에 글을 남기시려는 분들!!)

dldyddlwl 3년 전 1

채점 데이터를 잘 모르겠지만, 만약에 문서의 수가 0이 가능하다면

글쓴이님의 코드는 1이 나옵니다. (정답코드는 0이 나오는데, 문서의 수가 0이 가능한지 잘 모르겠습니다, 문제에 100이하라고는 되어있는데 당연히 자연수일 거 같기도 하고... )

gginn1234 3년 전 0

문서의 수가 0일 때, 결과가 0이 나오도록 해보았지만,,

여전히 "틀림" 이네요 ㅠㅠ

다른 반례에서 걸리는 것 같은데... ㅠㅠ

그래도 못난 코드 봐주셔서 감사합니다 ㅠ

dldyddlwl 3년 전 1

QType* L = (QType*) malloc(sizeof(QType));

L->Q = (*int) malloc(sizeof(int) * (k));

L->prior = (*int) malloc(sizeof(int) * (k));

int compare(const void* a, const void* b)

굵은 부분이 수정된 부분입니다! 이렇게 하니 정답이더군요. 제가 C를 잘 몰라서;; 죄송합니다.

어쨌든 문제는 저거였군요! 테스트케이스가 전부 맞은 이유가 있었네요 ㅋㅋ

gginn1234 3년 전 1

역시,,

저는 아직 부족한 듯 합니다..

사소한 부분에서조차 이렇게 놓치니까요..

L->Q = (int*) malloc(sizeof(int) * (k));

L->prior = (int*) malloc(sizeof(int) * (k));

위의 이 부분은 (*int) 이 아니라 (int*) 인 듯 싶어요!

잘못 된 부분 찾아주신 것도 감사한데,,

직접 돌려보시기까지 해주시니 정말 감사합니다~!! ㅠㅠ

dldyddlwl 3년 전 1

아 오타 죄송합니다 파이팅하세요!

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

문제

문제

출처

ICPC

반례가 있을까요...?

gginn1234 3년 전 1

gginn1234 3년 전 0

dldyddlwl 3년 전 1

gginn1234 3년 전 0

dldyddlwl 3년 전 1

gginn1234 3년 전 1

dldyddlwl 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말