Блог пользователя pritishn

[Help] CSES:Grid Paths , making all variables long long gives Accepted but using int gives TLE.
Автор pritishn, 4 года назад, По-английски

For the Grid Paths problem, if I use #define int long long and submit the solution, it gets accepted verdict, but using int gives time limit exceeded. How is this possible?

Link to accepted with long long : https://cses.fi/paste/6c2a837ed715717813be49/
Link to TLE with int : https://cses.fi/paste/1298e773dc80a66513be46/

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Run it locally and measure the time. Maybe both versions are close to TL and you just got lucky once.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I ran them locally 5 times ..
    flags : -Wno-unused-result -O2 -std=c++17

    using int
     0.74103 sec
    0.756871 sec
    0.79994 sec
    0.738276 sec
    0.733718 sec

    using long long
     0.691453 sec
    0.68186 sec
    0.689874 sec
    0.697802 sec
    0.683085 sec

    How can the long long version be faster? Have you ever encountered something like this?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      It is platform and compiler dependent. Usually the operations on types of target CPU's native word length are no slower (and usually faster) than the operations that might require casting the width to native size.

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        Oh, that explains it! I used custom invocation (on 32bit C++17) here on codeforces and it gave predicted results.

        long long = Used: 1014 ms, 0 KB
        int = Used: 561 ms, 4 KB

        Thanks Actium for the answer.

        → Ответить