It seems that codeforces compiles and runs submissions in a windows environment. This can produce some surprises to anyone who develops solutions under Linux.

(I have not checked the details of anything written here....)

CPU time and clock

A linux developer will believe that the clock function will return a good approximation of the processor time used by a program. In the codeforces environment this is occasionally untrue.

Reference: https://mirror.codeforces.com/blog/entry/85677

The solution is code along these lines: ~~~~~ long double cpu_time() {

if defined(_WIN32) || defined(_WIN64)

FILETIME creation_ft, exit_ft, kernel_ft, user_ft;
GetProcessTimes(GetCurrentProcess(), &creation_ft, &exit_ft, &kernel_ft, &user_ft);

auto extract_time = [](FILETIME ft) {
    return 1e-7L * (ft.dwLowDateTime | uint64_t(ft.dwHighDateTime) << 32);
};

return extract_time(user_ft) + extract_time(kernel_ft);

else

return (long double) clock() / CLOCKS_PER_SEC;

endif

~~~~~

Random numbers

A linux developer will read that the rand() uses the same code as the random() function, which produces a random number generator with a huge period (16 ** (2**31)). In the code forces environment rand() produces a cycle of random numbers with a period of 32768.

Reference:...