Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Fahmid_rng's blog

Getting TLE because of using bitset
By Fahmid_rng, history, 5 months ago, In English

In last Div-2 contest, my this code 377729532 got accepted where this submission 377724457 recieved TLE verdict. Logic of both code are exactly the same. But, in the TLE version, I used bitset and used string instead in the AC submission. But, note that I initialized bitset array in global scope. So, in the TLE version, my code should do at max $$$3N + 2\sum n + T(7 \cdot \frac{N}{w} + 9 \cdot 31)$$$ operations. Here, $$$T \le 10^4, N = 10^5 + 1, w$$$ is word size i.e $$$64$$$. So, it shouldn't take more than $$$1.3$$$ s at all. But, then, why am I getting TLE? Can anyone explain, please?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 months ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

https://codeforces.me/contest/2234/submission/377763172

It is better not to use std::cin for direct input into a std::bitset.

→ Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Out of curiosity, does it have the same issues if you directly use the bitset's string constructor? My guess is it mostly has to do with cin being used directly with the bitset (as you mentioned) as opposed to the constructor itself being slower than a manual for loop (which is what you submitted). (I'm refraining from submitting it myself to check as I have not seen the problem and don't want to incorrectly flag it as solved.)

    → Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Ohh, thanks a lot. From now, I will never use cin to read a bitset. I thought, maybe the bitwise operations were slow like O(N) instead of O(N/w). But, finally understood the actual pitfall.

    → Reply