appa   2년 전

맞추고나서 다른 분들의 소스를 보니... 왜 동작하는 건 같은 소스인데 제 O(n) 소스는 TLE가 나는거죠?ㅠㅠ

저게 TLE가 나서 O(1)짜리로 고쳐야 AC가 뜨더라구요. 그런데 O(1)로 일반식을 적으니까 계산 도중에 long long을 벗어나서 음수부터 계산하고 양수를 뒤에 계산해줘야하는 번거로움도 있었습니다.

appa   2년 전

위의 소스를 ACM-ICPC live archive에 제출하니까 2.5초로 AC가 뜨던데... 저기가 대회 공식 데이터를 쓰진 않는 것 같네요 :(

공식 데이터를 넣고 제 컴퓨터에서 돌리니까 7초 정도 걸리는 것으로 보아...

48cc63c1a51944d9e3b6114736ddfe9b.png

pichulia   2년 전

음...이 문제를 맞추지 못해서 함부로 테스트를 못하겠네ㅋㅋㅋㅋ

개인적인 생각입니다만... (ll)으로 int를 long long으로 캐스팅하는 부분에서 오래 걸리는것 같네용

appa   2년 전

말씀하신대로 캐스팅에서 문제가 생긴거였군요ㅠㅠ

아래 소스는 AC입니당

wookayin   2년 전

제가 추측하는 이유입니다.

  • BOJ는 32비트 CPU 를 사용하고 있는것으로 들었습니다 (아닐수도 있습니다).
    요즘 도는 대부분의 리눅스 서버들 (라이브 아카이브) 은 64비트 CPU 를 사용할 겁니다.
  • 당연한 말이지만, 하나의 레지스터에 담을 수 있는 word 길이가 다르기 때문에
    64bit integer 를 다루는 데 32비트 CPU와 64비트 CPU 의 연산당 클럭 수가 다릅니다. 당연히 64비트가 빠르겠죠.
  • 쉽게 말해 32비트에서는 int <-> long 캐스팅에 비용이 좀 비쌀 수도 있습니다...
    64비트에서는 별 차이 없는것으로 알고있습니다.

자세한 설명은 http://stackoverflow.com/questions/1941826/why-is-this-faster-on-64-bit-than-32-bit 이 글을 참고해보세요.

결론.. baekjoon 64비트로 업글좀..

wookayin   2년 전

위에 제가 약간 잘못된 말을 한것 같아서 정정합니다. (baekjoon 댓글 수정 기능이 필요해요 ㅠㅠ)

연산당 클럭 수가 다르다는건 좀 잘못된 말인것 같고 (물론 그 영향도 있겠지만...)
 64비트 레지스터를 사용할 수 있느냐에 따라 생성되는 기계어/어셈블리가 다른게 더 중요한 이유일것 같습니다.

로우레벨은 저도 아주 deep하게는 몰라서 여기까지만.. 

baekjoon   2년 전

저도 64비트로 옮기고 싶긴 한데... 서버를 옮기는게 무슨 복붙처럼 쉽게 되는 일이 아니라서 말이죠 ㅠㅠ

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