creatorysy   1년 전

모스로 풀 수 있다는 글을 보고 저도 모스로 풀어봤는데 시간초과가 뜹니다. 이 코드에서 FASTIO 도 사용해보고 의심스러워보이는 auto 문이나 구조체 내부의 오퍼레이터에 있는 pair 도 풀어서 쓰고 MOS 함수도 main 함수 안에 넣는 등 생각나는 모든 것을 해보았는데 여전히 안됩니다. 제 코드에서 추가적으로 최적화할 수 있는 방안이 있을까요?

kwakws0627   1년 전

25번째 줄 잘 보세요. 어딘가 이상합니다.

만약 같은 버킷 안에 있으면 내 y와 r.y를 비교해야 합니다.

 

추가로, 79번째 줄에서 답 출력할 때도 줄바꿈(\n)이 필요합니다.

creatorysy   1년 전

정말 감사합니다. 모스 안되는줄 알고 머지 소트 트리로 짜서 풀었는데 제가 구현을 이상하게 해서 그런거였군요.

그런데 아직도 왜 Qsqrt(N) 짜리 모스랑 QlogN 짜리 머지 소트 트리가 시간이 비슷하게 나오는지는 모르겠네요

kwakws0627   1년 전

Mo's vs merge sort tree 관련해서는 제가 전공자가 아니여서 잘 모르겠네요 ㅜㅠ

질문들 새로 파서 다른 분들께 여쭤보는게 나은거 같네요.

luckyandykang   1년 전

아마 머지 소트 트리의 연산량, 시간 복잡도에서의 상수항이 클 겁니다

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