Оценивать скорость программы по 4 тестовым числам — недостаточно. Легко может победить программа с более плохим «основным кодом», но с более удачным выбором значений таблицы.
Ну, вообщем, так и случилось. BarsMonster должен был рассказать про способ оценивания решения подробнее в своем предыдущем посте. Я думал, что нужно минимизировать худшее время работы, как это обычно надо в олимпиадном программировании. У меня код во многом похож с shadeware, тоже предподсчет 64 значений но, в отличии от него есть оптимизация, выкидывающая все четные числа. Я все время считал весь массив, и это стоило мне 1 места, так как в тестах в среднем надо было посчитать 0.41 массива, как результат — мой код на 12% медленнее. Если бы я написал цикл в 19 строчке не до N, а до (n-x+1)/2, то программа заработала в 2 раза быстрее.
Пока вы будете заполнять таблицу в памяти или обращаться к жесткому диску, я давно уже ответ посчитаю. Мне нужно меньше 1ms времени и 1MB памяти на тест.
Что такое UTF-8 последовательность? Clang поругался только на 2 символа, что в них особенного? При ограничении в 1024 байта естественно ожидать от участников экономии кода исходя из предположений, которые при данных ключах компиляции почти всегда верны. Да, я согласен, что предупреждения игнорировать не стоит, но в данной задаче это не критично. Лучше поищите логические ошибки в программах, это сложнее и увлекательнее, так как тестов было мало, наверняка они есть.
Я имел в виду extended character set. К чему строгое следование стандарту в данной конкретной задаче? Согласно стандарту, компилятор много чего мог сделать, но это не значит, что он должен по-умолчанию придираться ко всему подряд.
Все в пределах Extended ASCII Codes. Я компилировал перед отправкой, ошибок не было. Да, я понимаю, что это недопустимо в промышленном программировании, но эта задача имеет олимпиадный характер.
Без ограничений на размер решения была бы жесть! Можно написать решение за ~N^0.5 с предподсчетом за ~N(асимптотики с точностью до логарифмов). И тогда отделить решения было бы очень трудно. Я ничего не обфусцировал, и если бы написал цикл в 19 строчке не до N, а до (n-x+1)/2, то скорее всего, выиграл бы.
У меня тоже решето с предподсчетом. Компилятор ругался, потому что я использовал символы с кодами больше 127. Решение старался сделать максимально прозрачным) Кстати, кто еще хочет порешать похожие задачи, но килобайта мало, есть трудная задача как раз на блочное решето: www.spoj.com/problems/PRIMES2/. Учтите, там Pentium 3!
Ну, вообщем, так и случилось. BarsMonster должен был рассказать про способ оценивания решения подробнее в своем предыдущем посте. Я думал, что нужно минимизировать худшее время работы, как это обычно надо в олимпиадном программировании. У меня код во многом похож с shadeware, тоже предподсчет 64 значений но, в отличии от него есть оптимизация, выкидывающая все четные числа. Я все время считал весь массив, и это стоило мне 1 места, так как в тестах в среднем надо было посчитать 0.41 массива, как результат — мой код на 12% медленнее. Если бы я написал цикл в 19 строчке не до N, а до (n-x+1)/2, то программа заработала в 2 раза быстрее.
~N^0.5с предподсчетом за~N(асимптотики с точностью до логарифмов). И тогда отделить решения было бы очень трудно. Я ничего не обфусцировал, и если бы написал цикл в 19 строчке не доN, а до(n-x+1)/2, то скорее всего, выиграл бы.