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://codeforces.net/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() function uses the same code as the random() function, which produces a random number generator with a huge period(16 ** (2**31))of roughly $16^{2^{31}}$. In the code forces environment rand() produces a cycle of random numbers with a period of 32768. ↵
↵
Reference:...↵
↵
(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://codeforces.net/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() function uses the same code as the random() function, which produces a random number generator with a huge period
↵
Reference:...↵
