Привет кодфорсес. Сегодня я увидел что новичок с никнеймом Kevin0099 решил задачу C вчерашнего соревнования используя цикл фор. Я посчитал что его код при максимальных значених t, n, k, x его решение будет работать за 40 секунд (если я не прав поправьте меня в комментариях), вот его код
Hello codeforces. Today I saw that a newbie with the nickname Kevin0099 solved Problem C from yesterday's competition using the for cycle. I calculated that his code with maximum values of t, n, k, x, his solution will work in 40 seconds (if I’m wrong, correct me in the comments), here is his code
Сумма по всем n не превышает 2*10^5
Благодаря этому утверждению можно сказать, что суммарное количество операции, произведенным циклом for, так же не превысит 2*10^5.
Обратите внимание, что сумма n по всем тестам может превышать 2⋅10^5.
тем более один другой участник контеста запустил 1 цикл до к и у него было ограничение времени, а Kevin0099 запустил 2 цикла до к
Извиняюсь, как увидел черный жирный текст подумал что не превышает))
И в правду странно, даже если в ручную выставить максимальные тесты в запуске, все работает довольно быстро.
Так это ж магия прагм вроде обыкновенная
P.S. Да и цикл не зависит от внешних данных, то есть простая арифпрогрессия, наверняка и это оптимайзится легко
вот это функция делает его код гораздо быстрее auto stop = high_resolution_clock::now(); auto duration = duration_cast(stop — start);
Даже если убрать эту функцию, все равно работает быстро
the reason behind this code working is the fact that he uses
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
these lines of code, in some problems that are rated 2800-3100 there are old tasks that have tests that can be passed using these types of code optimization. Perhaps this was also the task that was passable via pragmas here is the link to the code without pragmas (identical, sent by me, but without pragmas) submision
прочитай что делают прагмы и пойми что асимптотика — не показатель