글 읽기 - 범위를 수정하거나 데이터를 추가해주세요.

djm03178 5년 전 0

문제에는 N <= 1000이라고 되어 있지만, 실제로는 ~~이진탐색 비스무리한 걸 해보니~~ 최대 데이터는 N=50임을 확인했습니다.

정답을 받은 제 AC 코드는 (그리고 아마 다른 분들 코드의 상당수는) 단순 DFS를 통한 이분 매칭으로, 최악의 경우 O(N^3)이 됩니다.

만일 이러한 풀이를 허용하는 것이 문제의 의도라면 범위를 수정해주시고, 범위를 유지해야 한다면 다음과 같은 데이터를 비롯해 N이 큰 데이터들을 일부 추가해주세요. 로컬에서 2초 정도 걸렸습니다.

#include <cstdio>
using namespace std;

int main()
{
	int n = 1000;
	int m = 2000000000;
	FILE *fp = fopen("in.txt", "w");
	fprintf(fp, "%d\n", n);
	for (int i = 0; i < n; i++)
		fprintf(fp, "%d %d %d\n", m, m, m);
	fclose(fp);
}

portableangel 5년 전 1

https://community.topcoder.com...

문제의 원본으로 보이는데, n이 50이네요. 아마 옮겨오는 과정에서 오류가 있었던것 같습니다.

startlink 5년 전 1

1,000 데이터를 추가하려고 생각해서 그런 제한을 뒀으나, 그러지 않은 것 같습니다.

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

문제

문제

출처

ICPC

범위를 수정하거나 데이터를 추가해주세요.

djm03178 5년 전 0

portableangel 5년 전 1

startlink 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말