https://codeforces.net/contest/1620/submission/139785121
Here is my code, anyone can find this code is O(n) time complexity. I tried to read the string using different read methods, but I got a verdict of exceeding the time limit at the fifth test point.
https://codeforces.net/contest/1620/submission/139786622
After converting the FPC code to C++ code, I get the Accepted verdict.
I would like to know why FPC is getting out of time limit.
Thanks in advance for reading and replying.
strlenis $$$O(string_{length})$$$ no matter how many times you run it, not $$$O(1)$$$, so not even your C++ code won't run in linear time per test.You are ignoring C++'s compiler optimization, where the result of strlen is automatically saved before the loop.
Sorry, I didn't know that, but your point is still weird. Maybe you will need to use a judge which evaluates your code with
-O0, or maybe you will have to use a compiler which doesn't employ this optimization.I looked online now and your point is in a comment, but other people argue that having the string declared globally or not having the string
const char *could stop the optimization from taking place.I still think that using
strlenlike this in a loop condition is dumb and could easily backfire, especially when you can usestd::stringwithsize()orlength()or evenfor (int _ = strlen(s), i = 0; _; _--, i++)I merely agree with your point. However, there are 2 things I want to notice:
1) Providing the code is executed with
-O0, it runs in $$$O(n^2)$$$, and the upper bound for output is the same. So, in fact, the complexity is fine.2) I personally do not like the style
for (int _ = strlen(s), i = 0; _; _--, i++). Too easy to make a mistake. I would prefer smth like this:for (int _ = strlen(s), i = 0; i < _; ++i).I agree with both of your arguments! Your way of writing the
foris objectively better, I just wanted to show an example.It seems that outputting string character by character is way too slow in pascal. I've copied your code, replaced many outputs with one and got AC: 139885829 (
out += chr(13)is the way to append new line symbol to the string).