fastru   2년 전

브루트포스 알고리즘을 사용한 제출번호 17701904 코드가 통과됩니다.

C++20(Clang)의 속도가 특히 빨라서 발생하는 문제이기도 합니다. 언어별 시간제한을 달리하거나 시간제한을 1초 정도로 줄여주세요.

(수정) 시간제한 수정이 힘들다면 테스트케이스를 추가해주세요. 브루트포스 알고리즘을 사용하면 아래와 같은 최댓값으로 구성된 테스트케이스에서 시간초과가 날 것으로 예상됩니다.

djm03178   2년 전

그러면 루트로그인가에 푼 제 코드가 날아갑니다 흑흑

fastru   2년 전

기여를 보니까 많은 분께서 간과하시는 것 같던데, 이 문제의 출제 의도는 루트로그가 아닙니다.

수열과 쿼리 18(14504)과 이 문제의 가장 큰 차이는 A의 범위입니다. A의 범위가 10^4까지이기 때문에 제곱근 분할법을 사용한 후 전처리를 통해 각 수의 개수를 카운팅하여 풀 수 있습니다.

위에서 말한 방을 사용해 풀면 fast I/O를 안 했어도 700ms 정도로 여유롭게 통과합니다. 맞은 사람 1페이지 목록에도 위에서 말한 방법을 사용한 코드가 많습니다.

djm03178   2년 전

제가 정해로 풀었다는 건 아니고, 나이브가 뚫리지 않았다면 굳이 시간 제한을 조정하려고 할 이유도 없었을 텐데 그걸 막으려다 적당하게 뚫어낸 풀이들도 같이 터지는 게 좀 억울해서(?) 푸념한 겁니다.

herdson   2년 전

이거 제가 알기론 clang 때문에 시간 바꾸기는 애매해서 냅두고 있지 않나요?

그리고 이름은 기억이 잘 안나지만 clang으로 나이브하게 풀 수 있는 쿼리문제를 모아둔 문제집도 있는 것으로 압니다.

fastru   2년 전

C++20(Clang)이 비정상적으로 빠르지 않은 이상, 테케를 좀 극단적으로 주면 통과할 수 없는 코드인데.. 테케가 좀 빈약해서 발생하는 문제 같기도 하네요.

fastru   2년 전

질문의 요점을 '테스트케이스 추가'로 수정했습니다.

djm03178   2년 전

아마 clang이 사용하는 특정 최적화 기법 때문에 코드상에 보이는 것보다 훨씬 빠른 연산을 CPU 명령어 선에서 만들어내는 것으로 알고 있습니다.

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