pichulia   4년 전

시간초과가 나야 하는 채점번호 : 43359955

아래 코드로 생성되는 데이터를 추가해주시길 바랍니다. 정답은 50000 입니다.

std::unordered_set 와 std::unordered_map 의 clear() 함수에 버그가 있습니다.

이전에 N 개의 데이터를 추가한 적이 있다면, clear 연산을 호출할 때마다 O(N) 의 시간이 소모됩니다.

따라서 ENTER 가 들어올 때마다 clear() 를 하는 코드는 의문의 TLE 를 받게 될 것입니다.

초심자를 사랑하는 곰곰컵의 컨셉에 맞춰서, 대회중에는 일부러 이 데이터를 추가하지 않았습니다.

하지만 대회는 끝났습니다. 교육의 시간입니다.

감사합니다.

doju   4년 전

지적하신 clear() 취약점은 정확히는 원소의 개수가 아니라 버킷의 개수에 비례하는 시간이 걸리기 때문에, n2 = 50000은 최악의 데이터는 아닙니다. 실제로 unordered_set을 사용하는 코드를 Clang으로 실행할 경우 이 데이터를 안정적으로 통과합니다.
더 강한 데이터를 만들려면 n2 = 42044(for GCC)와 n2 = 53201(for Clang)을 사용하면 됩니다.

참고로 최악의 데이터를 추가하더라도 두 컴파일러 모두 약 1500ms만에 동작하므로, 확실히 시간 초과를 내겠다면 시간 제한을 줄이고, 아량을 베풀겠다면 시간 제한을 늘리는 것이 바람직해 보입니다.

pichulia   4년 전

다음과 같이 생긴 O(N^2) 코드가 1450ms 정도에 동작하는 것을 확인했습니다.

아량을 베풀 수 없을 것 같습니다.

startlink   4년 전

재채점했습니다.

yugioh   3년 전

왜 자꾸 틀리나 했더니 clear 연산이 O(1)이 아니군요. 좋은 공부가 됐습니다. 감사합니다.

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