Hi Codeforces!
Today I'm writing this blog to express my sad feelings about my lack of knowledge. I was pretty sure that a testing system does around 1e9 operations per a second. That's what everyone have been telling me for last 2 years. The problem, as I think, is that I didn't really question myself what "the operation" is. That's why I made an unsuccessful hack attempt in today's round. Some newbie wrote the code for problem A using this:
for(int i = 0; i < m; ++i){
for(int j = 0; j < i; ++j){
if(B[i] == B[j]) {...}
}
}
m is up to 5*1e4, so even these 5 lines make around 5*1e4*2.5*1e4 = 1.25*1e9 operations. Obvious TL, as I thought. But it wasn't (the solution soon got AC on final tests). I think that by saying "the operation" people actually mean some arithmetic operation like plus, minus, maybe divide, while logic operations may take smaller time. Again, this is only my assumption, and if you know the real explanation to this situation, please write it in the commentary section.
Auto comment: topic has been updated by shevlopmes (previous revision, new revision, compare).
for(int i{}; i<n; ++i) for(int j{}; j<n; ++j) exit(0);the line "exit(0);" ends the whole programm, so this code iterated only once.
I have known that while solving problems it is safe to assume 1e8 operations per sec in C++. There are some operations which are slower than other operations. It usually depends how cache-friendly your operations are (It can sometimes do 2e9 — 3e9 operations or more as well) . Some operators like % (modulo) are heavier than let's say addition, subtraction.
In case of the code you mentioned, it depends on the code inside the if.
But if it is very light, then it can in fact do more than 1.25 * 1e9 operations.
Here is a recent blog related to this...
Thank you!
Some light operations(like addition or bitwise operation) can indeed be very fast. If you add some pragmas, you can do more than a few billions of them.
However, usually this doesn't work if the code is a little bit complex.
Thank you! I've heard about pragmas as some magic solution but never used them. I'll check it
Then you can use avx instructions and be able to perform $$$10^{10} - 10^{11}$$$ operations per second, depending on the operation.