17410번 - 수열과 쿼리 1.5
브루트포스 알고리즘을 사용한 제출번호 17701904 코드가 통과됩니다.
C++20(Clang)의 속도가 특히 빨라서 발생하는 문제이기도 합니다. 언어별 시간제한을 달리하거나 시간제한을 1초 정도로 줄여주세요.
(수정) 시간제한 수정이 힘들다면 테스트케이스를 추가해주세요. 브루트포스 알고리즘을 사용하면 아래와 같은 최댓값으로 구성된 테스트케이스에서 시간초과가 날 것으로 예상됩니다.
그러면 루트로그인가에 푼 제 코드가 날아갑니다 흑흑
기여를 보니까 많은 분께서 간과하시는 것 같던데, 이 문제의 출제 의도는 루트로그가 아닙니다.
수열과 쿼리 18(14504)과 이 문제의 가장 큰 차이는 A의 범위입니다. A의 범위가 10^4까지이기 때문에 제곱근 분할법을 사용한 후 전처리를 통해 각 수의 개수를 카운팅하여 풀 수 있습니다.
위에서 말한 방을 사용해 풀면 fast I/O를 안 했어도 700ms 정도로 여유롭게 통과합니다. 맞은 사람 1페이지 목록에도 위에서 말한 방법을 사용한 코드가 많습니다.
제가 정해로 풀었다는 건 아니고, 나이브가 뚫리지 않았다면 굳이 시간 제한을 조정하려고 할 이유도 없었을 텐데 그걸 막으려다 적당하게 뚫어낸 풀이들도 같이 터지는 게 좀 억울해서(?) 푸념한 겁니다.
이거 제가 알기론 clang 때문에 시간 바꾸기는 애매해서 냅두고 있지 않나요?
그리고 이름은 기억이 잘 안나지만 clang으로 나이브하게 풀 수 있는 쿼리문제를 모아둔 문제집도 있는 것으로 압니다.
C++20(Clang)이 비정상적으로 빠르지 않은 이상, 테케를 좀 극단적으로 주면 통과할 수 없는 코드인데.. 테케가 좀 빈약해서 발생하는 문제 같기도 하네요.
질문의 요점을 '테스트케이스 추가'로 수정했습니다.
아마 clang이 사용하는 특정 최적화 기법 때문에 코드상에 보이는 것보다 훨씬 빠른 연산을 CPU 명령어 선에서 만들어내는 것으로 알고 있습니다.
댓글을 작성하려면 로그인해야 합니다.
fastru 2년 전
브루트포스 알고리즘을 사용한 제출번호 17701904 코드가 통과됩니다.
C++20(Clang)의 속도가 특히 빨라서 발생하는 문제이기도 합니다. 언어별 시간제한을 달리하거나 시간제한을 1초 정도로 줄여주세요.
(수정) 시간제한 수정이 힘들다면 테스트케이스를 추가해주세요. 브루트포스 알고리즘을 사용하면 아래와 같은 최댓값으로 구성된 테스트케이스에서 시간초과가 날 것으로 예상됩니다.