요거 값 다 2147483648을 더해서 0 이상의 수로 바꿔주고 radix sort로 풀면 std::sort보다 빠를거 같아서 해봤는데

std::sort는 800MS, radix sort는 시간초과가 떠서요

0 이상의 수로 만들어주는 과정에 쓴 덧셈 연산이 느리거나, 큐 푸시/팝 연산이 느리거나

아니면 구현 자체가 멍청했을 가능성도 있지만 ㅠㅠ

std::sort가 어떤 원리로 동작하길래 이렇게까지 빠른지 궁금해서요

movie_jo   2년 전

2분 32초부터 보시면...

pichulia   2년 전

long long 으로 연산하는건 생각보다 시간이 오래걸리는 일입니다.

그래서 unsigned int로 계산하면 적당히 빨라지지 않을까 하는 생각에서 radix sort를 짜봤는데..역시나 TLE더라고요ㅋㅋㅋ

그래서 이런저런 시도를 해본 결과 아리의 코드가 996ms로 통과했습니다.

i++ 대신 ++i 를 쓰고

뭐 이래저래 삽질을 해야만 겨우겨우 얻을 수 있는 AC네요

포기하고 그냥 std::sort 씁시다.

오와..

감사합니다 ㅋㅋㅋㅋ

baekjoon   2년 전

996이면 채점 머신의 상황에 따라서 TLE날 수도 있는 시간이네요... 재채점을 한다면...::::::

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