기본적으로 곱셈보다 나눗셈이 느리고, int 보다 long long int 가 느린건 맞지만, 막 시간이 2~3배 이상 차이나고 이러는 정도는 아닙니다.
제 생각에는 43161208 번이 정답을 받은 이유는., part[MOD0] 를 사용해서, hash 중복체크 확인 절차를 약 O(1)에 처리한 것이 시간초과가 나지 않은 이유로 보입니다.
아마 43148896 가 시간초과가 난 이유는 std::map 을 사용했기 때문으로 보이며.. 43161208 와 비슷한 방식으로 풀면 정답을 받을 것으로 보입니다.
rootsquare 1년 전
Hash/Rolling Hash function을 사용하여 문제를 풀긴 풀었는데, 처음에 hash를 구할 때 제수(mod)를 엄청 크게(100억 이상의 소수) 잡았더니 계속 시간 초과가 나서
적당히 큰 소수(10^6+3,10^6+33)으로 hash 리스트를 만들어서 풀었습니다.
혹시 큰 수는 서버에서 처리하는데 시간이 오래 걸리나요..?
제출번호 43148896 ->시간 초과
제출번호 43161208 -> 맞았습니다