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?
https://codeforces.me/contest/2234/submission/377763172
It is better not to use std::cin for direct input into a std::bitset.
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.)
https://codeforces.me/contest/2234/submission/377804377
You are right.
Ohh, thanks a lot. From now, I will never use
cinto read abitset. I thought, maybe the bitwise operations were slow likeO(N)instead ofO(N/w). But, finally understood the actual pitfall.