9개의 댓글이 있습니다.
-
-
zzerross -
JongMan 님 조언을 참고해서 추석 지나고 그 함수를 이틀째 다시 보고 있는데, TLE해결이 않되네요...ㅜ.ㅡ
1) 전역 rmv()에서 "지배되는 점을 찾는 것, td::lwr()" 과 실제 "삭제하는 것, td::rmv()"이 두번 탐색을 야기시킬 것 같긴 한데,
하나로 합쳐보는 작업도 도통 잘 않되네요.
treap 구현을 일반적인 형태로 유지하고 싶기도 하구요.2) 작은 random data들로 꽤나 다시 검증 해보긴 했습니다만,
혹시 전역 rmv()의 문제가 성능이 아니라, 답이 잘못나오게 되는 것을 말씀하신 걸까요?3) STL없이 treap을 구현하는 것이 성능 상 한계가 있는 건지,
10년 전 link
-
-
-
zzerross -
드디어...찾았습니다...
최다 실패를 기록했지만, 처음으로 가장 빠른 답안에 랭크되어 기쁘네요.
조언해주신, JongMan님, Being님께
감사하는 마음, 반성하는 마음으로 오답 정리해봅니다. ㅜ.ㅡ1)종만님 지적해 주신,
전역 rmv()에서 불필요한 검사를 했던 것이 주요 포인트 였습니다.
조금이라도 능력것 풀어보려고,
책의 코드를 자세히 보지 않으려고 하는데,
항상 쉽지 않네요.
2)그 다음으로 treap insert를 split & merge로 구현했다가,
TLE를 극복해보자, priority에 따라 leaf에 달아주기만 하도록 했는데,
계속 insert되는 경우엔,
이게 더 성능저하를 가져와서,
전역 rmv() 수정 후에도 TLE를 야기시켰네요.
3)new를 하는 것과 않하는 것이 100ms 정도 차이나네요.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
zzerross
NERD2
문제를 풀고 있는데, TLE 극복을 못하던 중에,
아무리 분석을 해봐도 로직에서의 Big O를 못찾고,
구간 별 측정을 해보니, scanf()에서 시간을 많이 소요하는 거 같습니다.
입력 관련 AOJ글들을 찾아보니,
scanf()가 그래도 빠른 입력인 거 같은데요. 더 빠른 방법이 있을려나요?
정말 로직 상에 문제가 있는 건지 답답해서 질문드려봅니다.
로직, 코딩 상으로 아래의 것들을 변경해서 측정해보 았는데 차이가 없더라구요.
성능 측정:
Visual studio 2012
release mode
...
555740
725022
398417
728733
total: 1388ms
scanf: 1279ms
debug mode
555740
725022
398417
728733
total: 7098ms
scanf: 6160ms
코드는
10년 전