글 읽기 - 특별히 어긋나는 테스트케이스가 없는데 틀렸다고 나옵니다.

muscj7 5년 전 0

제가 테스트해보기로는 특별히 어긋나는 테스트케이스가 없는데 틀렸다고 나옵니다.

혹시 예외 상황이나 제가 잘못이해한 것이 있을까요?

일단 문제를 풀며 헷갈렸던 기본적으로 처리했던 로직을 말씀드리겠습니다.

본 문제는 3가지 케이스의 답 형식이 있습니다.

올바른 등수 출력
? 출력
IMPOSSIBLE 출력

입력으로 ' 상대적인 등수가 바뀐 쌍' 예) B A가 주어질 때, 저는 이렇게 처리했습니다.

B가 이미 A보다 높은 등수이다. -> 입력을 다 받은 후 "IMPOSSIBLE" 출력

B를 제끼는 놈들(A1, A2, A3..)들을 차수(등수에 의존) 순서대로 세웠을 때, 옆 팀과의 차수 차이가 1이 아니다. -> "?"

-> (제낀 놈들의 수를 n이라 할 때 1~n의 합과 A1차수-B차수~An차수-B차수의 합이 같은가 다른가로 판단했습니다.)

otherwise -> 변경된 등수 출력

무엇이 잘못되었을까요? ..ㅠ.ㅠ

#include<stdio.h>
#include<vector>

using namespace std;

const int MAX_TEAM = 501;

vector<int> indegree;
vector<int> dismiss_count;
vector<vector<int>> dismiss;

int main() {

	int T;
	scanf("%d", &T);

	while (T--) {
		int n, m;
		// 팀의 수와 팀순위 순서 입력
		indegree.clear();
		indegree.resize(MAX_TEAM);
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			int t_i;
			scanf("%d", &t_i);
			indegree[t_i] = i; // 순서대로 차수 부여
		}

		// 상대적인 등수가 바뀐 쌍의 수와 바뀐 내용 입력
		dismiss_count.clear();
		dismiss_count.resize(MAX_TEAM);
		dismiss.clear();
		dismiss.resize(MAX_TEAM);
		scanf("%d", &m);
		bool impass = false;
		for (int i = 0; i < m; i++) {
			int A, B;
			scanf("%d %d", &A, &B);
			dismiss[B].push_back(A); // B를 제낀 A들을 저장
			dismiss_count[B]++;      // B를 제낀 A들의 수를 저장

			if (indegree[A] < indegree[B]) { // 이미 A팀의 등수가 더 앞에 있으면
				impass = true;
			}
		}
		if (impass) { // 입력 값 중 이미 A팀의 등수가 더 앞에 있었으면
			printf("IMPOSSIBLE\n");
			return 0;
		}
		
		// algorithm : 등수 변화 확인 		
        // 같은 B에 대한 A값이 들어올 때,
        // B를 제낀 (A들의 각 차수-B의 차수)를 sum한 것은 
        // A의 개수를 max로 생각하여 '1, .., max'의 합을 구한 것과 같아야 올바른 순위 변동이라 판별함.
		// 그렇지 않으면 "?" 출력.
		for (int i = 1; i <= n; i++) {
			if (dismiss[i].size() == 0)
				continue;

			int request = (1 + dismiss_count[i]) * dismiss_count[i] / 2, respon = 0;
			for (int k : dismiss[i]) {
				respon += (indegree[k] - indegree[i]);
			}

			if (request == respon) {
				for (int k : dismiss[i]) {
					indegree[k]--;
				}
				indegree[i] += dismiss[i].size();
			}
			else {
				printf("?\n");
				return 0;
			}
		}

		// 같은 차수를 갖는 팀은 없으므로, '등수 : 차수'를 '차수 : 등수'데이터로 변경(가능)
		int rank[MAX_TEAM];
		for (int i = 1; i <= n; i++) { // i는 팀, 
			rank[indegree[i]] = i;
		}

		// 변경된 등수 출력
		for (int i = 0; i < n; i++) { // i는 팀, 
			printf("%d ", rank[i]);
		}
	}

	return 0;
}

djm03178 5년 전 1

한 케이스에서 IMPOSSIBLE이나 ?가 나오더라도 다음 케이스를 계속 입력받아야 하고, 등수를 출력한 후에는 개행 문자를 출력해야 합니다.

muscj7 5년 전 0

한 케이스가 다 입력될 때마다 후 결과가 출력되도록 했고,

등수 출력 시 마지막에 개행도 했구

IMPOSSIBLE이나 ?를 출력하고도 retuurn하는것이 아니라 continue를 통해 다음 테스트 케이스의 while을 수행하도록 변경했는데도 안되네요..ㅠ.ㅠ 흠..

while(T--)
{
    
    .. 일부 생략 ..
        
    // 등수 출력 부분
    for (int i = 0; i < n; i++) { // i는 팀, 
        if (i == n - 1)
            printf("%d\n", rank[i]);
        else
            printf("%d ", rank[i]);
    }
    
    // IMPOSSIBLE 출력 부분
    if (result_code == 1) { // 이미 A팀의 등수가 더 앞에있으면
        printf("IMPOSSIBLE\n");
        continue;
    }
    
    // ? 출력 부분
    if (result_code == 2) {
        printf("?\n");
        continue;
    }  
    
    .. 일부 생략 ..
        
}

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

문제

문제

출처

ICPC

특별히 어긋나는 테스트케이스가 없는데 틀렸다고 나옵니다.

muscj7 5년 전 0

djm03178 5년 전 1

muscj7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말