로직이랑 구현은 맞으셨는데 실수연산이 문제였던 거 같습니다.
코드에서 floor, sqrt, 실수 나눗셈 부분을 최대한 정수 나눗셈으로 바꿔주니 AC를 받네요.. (코드 : http://boj.kr/01697584a00940cb...)
+) Mo's에서 sqrt값은 처음에 Sq = int(ceil(sqrt(L)))로 구해서 상수로 사용하거나, Sq = 300처럼 고정시켜서 사용하시면 좋아요. 입력 제한이 100,000이면 sqrt(100,000)에만 맞춰서 코드를 짜면 그보다 작은 테케는 시간복잡도가 O(sqrt(n))은 아니더라도 알아서 시간 내에 돌아가서 괜찮습니다.
yanghj1490 2년 전
기본적으로 Mo's 알고리즘을 사용하고,
K개의 Deque에 각 A[i]의 인덱스를 저장하고,
Front-Back 값 역시 평방 분할을 이용해서 관리했습니다.
근데 WA(...)를 맞습니다.
크기가 작은 예제들은 많이 넣어봤는데
틀린 부분을 제 눈으로는 찾을 수가 없습니다,,
도와주시면 감사하겠습니다.
반례나 틀린 부분 지적 부탁드립니다,,
코드: http://boj.kr/c482ea8919414c0b...