I was solving this problem and I got AC. While I was solving the problem, I had some cerr's and I commented them out when submitting. After getting AC, I wanted to experiment if uncommenting those cerr's would have a difference in runtime. Lo and behold! The difference was huge. Take a look at these two submissions. 100116835 is the AC and 100116299 is the TLE. The AC runs in 62 ms and the TLE is over 1000 ms. Now I have questions. Does Codeforces use the standard error stream? Why does this affect my runtime? All the comments are print statements and even if they were outputted to standard output stream, this wouldn't cause TLE. Why, why, why?
i think it was for this reason
trav(i, hld) { //cerr << i << ' '; //}
100120172. I commented out the trav(i, hld) { cerr << i << ' '; }. But it is still TLE. That's not the problem.
I'm not sure what's surprising about this.
cerr
is a stream that exists during grading but isn't used to determine your verdict. You can just think about it ascout
but not looked at by the grader. And when you flush an out stream 3e5 times (you cerr endl every time in your two main loops), I wouldn't be too surprised with a TLE.But it ain't endl it is "\n".
Oh oops. Maybe I should've read macros more carefully.
Anyways,
cerr
is flushed whenever you use the<<
operator, asunitbuf
is set. You can probably google for more information.