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

Автор Marine7, история, 7 лет назад, По-английски

On POI, there is a special testing environment, which assumes equal execution time of every instruction (one clock cycle each), the count of the cycles is then divided by some number which mimicates the real CPU cycle capabilities, to get the runtime.

Could you (specifically in C++) take somehow advantage of this testing system property, and write your programs in a style, which generally uses more costly instructions, but fewer of them, as to make the execution time faster in this environment?

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can you please elaborate on which judge this is? It seems very strange, what does the phrase "assume equal time of every instruction" mean? They look at how many instructions you make? What is an instruction defined as? It would be nice if you can elaborate. Thanks.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Instructions are each individual assembler commands, each counts as 1 instruction, except for REP, REPE, REPZ, REPNE, REPNZ.

    The number of called instructions is counted during execution using Intel PIN. Then, the number of instructions is divided by 3GHz for example, so 3 billion, and that's how the final time result is received I suppose.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I don't think that's how it works (at least on Codeforces).

      Otherwise submitting the same code twice should result in exactly the same execution times, but it doesn't.

      Also counting e.g. integer and floating point operations both as 1 would be weird.

      According to your logic, something like this http://codeforces.com/blog/entry/54753 couldn't happen.

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

        Yes, as I wrote in the main text, I'm talking about a special testing environment used on POI.

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

Is the list of "instructions" that count as one clock cycle available?

Sending data to disk and allocating memory would be the most costly operations I can think of right now: -Creating a lot of pointers (this is seen in implementations like an implicit segment tree in an array or a explicit segment tree with pointers, where getting a chunk of memory (array) at once is more efficient) -Flushing data to disk with cin and cout (if this counts as one cycle, you can use cin and cout instead of scanf and printf aka fast I/O without penalty (or just don't have to use the cin.tie, cout.tie, sync_with_io... lines)

Other than those, there would be microoptimizations like: -x << 2 is faster than x * 2

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Every instruction except for instructions prefixed with REP, REPE, REPZ, REPNE, REPNZ take one cycle.

    The ones above take as many cycles, as the number of iterations.