joonas   2년 전

안녕하세요.

단순한 정렬 문제인데, cin, cout, sort 밖에 없는 소스에서 시간초과가 나더군요.

cin을 scanf로, cout을 printf로 바꾸니 324MS로 맞긴 했지만

N의 범위가 1 <= N <= 1,000,000 이고 시간제한이 1000MS 라 당연히 될 줄 알았습니다.

O( 2n + logn ) 인데 시간초과 받아서 충격먹었습니다.

언어마다 시간을 정하기에 애매하고 힘든 걸 알면서 이런 글 남겨서 죄송합니다.

O( 2,000,006 ) 이 1000MS에서 시간초과 났다는 말을 괜히 길게 적었네요.

잘 고려해주시기 바라겠습니다 ㅎㅎ

WeissBlume   2년 전

std::sort의 시간 복잡도는 O(nlogn)입니다. 또한 cout의 경우 endl이 나올 때마다 버퍼를 비우는 등의 부하가 발생하기 때문에 이것만 "\n"으로 바꿔도 많이 빨라질 것 같습니다.

만일 이래도 시간초과가 난다면 ios::sync_with_stdio(false);를 main 시작부분에 적어보세요.

WeissBlume   2년 전

ios_base::sync_with_stdio가 맞군요; 실수

yukariko   2년 전

좋은 정렬함수의 시간복잡도는  logn이 아닌 nlogn 으로 알고있습니다.

음.. 그리고 printf,scanf에서 324MS가 나왔다면, cin,cout의 처리속도가  printf,scanf의 5배정도만 되도

1000MS를 넘지 않을까요?

제 생각은 그렇습니다.

yukariko   2년 전

"\n"으로 바꾸니 accept 가 뜨는데 ios_base::sync_with_stdio(false)를 넣으니 런타임에러가 떠버리네요

이렇게 넣는것이 아닌가요?

joonas   2년 전

아 ㅋㅋ nlogn 인데 제가 착각했네요. 감사합니다 ㅎ

제가 고려해달라고 한 부분은, C++을 시작하고자 하시는 분 혹은 단련하고자 하시는 분들이 당연스레 cin, cout을 사용할텐데

마치 이것이 문제의 함정처럼 숨어있어서 원인불명이 될까 우려됩니다. 시간제한에 좀 더 자비를 주심이 어떠신가요

yukariko   2년 전

시간제한을 늘린다기 보단 

http://www.acmicpc.net/help/judge

이런 페이지 등에 언급을 하면 될것같네요.

cin cout 때문에 시간제한을 늘려야 하는것은, 비단 이 문제에만 적용되는 사안은 아니기 때문에 다른 문제에도 적용되어야 할 탠데,

입력이 거의 없음에도 시간초과가 발생할 수 있는 문제가 매우 많기 때문에 무리라고 봅니다..

그렇다고 입력이 많은 문제또한 많기 때문에 모든 문제를 다 찾기도 힘드니까요.

yukariko   2년 전

최근에 다른 분이 작성하신 python에도 비슷한 문제가 있었고, 예전에 자바에도 그러한 문제로 질문이 올라온적도 있었고,

심지어 C의 scanf로도 TLE가 뜬 적이 있었습니다.

C++의 경우만 해당되는 문제가 아니기 때문에 역시 시간제한을 늘리는것은 바람직하지 않은것 같네요.

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