
Из 183 решений у 11 был превышен допустимый размер решения, в 19 случаях — не удалось скомпилировать (об этих ошибках подробнее ниже). Далее 47 дали неправильные ответы на простых тестах (1..1000000), 8 не успели посчитать ответ за минуту (образец решения из условия задачи для 1млн работал 5 минут 36 секунд).
На сложных тестах — 5 решений выдали неверный ответ, и 12 — не уложились в одну минуту. 86 — успешно прошли все тесты.
Если кто потерял, вот топик о старте соревнования с условиями задачи.
О тестах и тестировании
Тестировалось все банальными скриптами, самая трудоёмкая операция — сохранение руками решений из почты (и повторные имена файлов… 42 штуки main.cpp....). Это видимо один из тех случаев, когда написать web-приложение для приема решений быстрее, чем разгребать тонны почты.Результаты тестирования — складывались в MySQL, откуда строилась таблица результатов.Простые тесты:
function do_test($input, $expected_output)
{
global $task_id;
exec("echo '$input' | Solutions2/bin/$task_id &2>1", $output);
if(count($output)==0)return false;
return(strcmp($output[0], $expected_output)==0);
}
$result = do_test("10","17") && do_test("1","0") && do_test("1000","76127") && do_test("100000","454396537") && do_test("1000000","37550402023");
Сложные тесты:
Оценивалось усредненное время выполнения (т.е. время выполнения для 4-х разных входных значений, деленное на 4). 3 самых быстрых решения тестировались со 100-кратным повторением — чтобы получить более точное время работы (отличие от одиночного прогона в пределах 1%).
$start_time = microtime (true);
//for($i=0;$i<100;$i++)
$result = do_test("980000000","23783220704190493") && do_test("1051174931","27269025983026043") && do_test("891728152","19783994900202129") && do_test("761987760","14559966509022149");
$end_time = microtime (true);
Таблица результатов
Коллеги, поднажмем на инвайты:№ | Habraname | Нужен ли инвайт | Результат | System ID |
---|---|---|---|---|
1 | @shadeware | Уже нет | 0.035053772330284 сек. | 48 |
2 | @mikhaelkh | Уже нет | 0.039169362783432 сек. | 41 |
3 | @Icemore | Уже нет | 0.068273649811745 сек. | 129 |
4 | @ripatti |
Уже нет | 0.11206769943237 сек. | 8 |
5 | @kbxxi |
Уже нет | 0.15401327610016 сек. | 156 |
6 | @monoid | Уже нет | 0.22840601205826 сек. | 69 |
7 | @Zver1992 | 0.23262423276901 сек. | 133 | |
8 | @Mrrl |
0.37099504470825 сек. | 178 | |
9 | @Staker | Да | 0.66007524728775 сек. | 171 |
10 | @SyDr |
Да | 0.93328875303268 сек. | 78 |
11 | @vbarinov |
Да | 3.2648342847824 сек. | 108 |
12 | @vanla |
Да | 3.3831697702408 сек. | 19 |
13 | @MaSaK |
Да | 3.4151287674904 сек. | 20 |
14 | @dark1ight |
3.5476635098457 сек. | 36 | |
15 | @udalov | Да | 3.8905065059662 сек. | 116 |
16 | @bklim |
4.3489827513695 сек. | 149 | |
17 | @cfighter |
4.4272682070732 сек. | 11 | |
18 | @VladVR |
4.7588297724724 сек. | 89 | |
19 | @borozdinKirill |
4.775633752346 сек. | 109 | |
20 | @ZhekSooN |
4.8941134810448 сек. | 122 | |
21 | @madkite | 4.9126330018044 сек. | 114 | |
22 | @akazakow |
5.208831012249 сек. | 45 | |
23 | @mingrief | 5.2523249983788 сек. | 179 | |
24 | @pasky |
5.9874464869499 сек. | 5 | |
25 | @ewnd9 |
6.024626493454 сек. | 183 | |
26 | @gnhdnb |
6.0333037376404 сек. | 158 | |
27 | @through_horizon | 6.2488570213318 сек. | 21 | |
28 | @kosmos89 |
6.2885909676552 сек. | 126 | |
29 | @Nickel | 6.36874127388 сек. | 42 | |
30 | @infsega |
6.4502172470093 сек. | 33 | |
31 | @shuternay | 6.4606020450592 сек. | 6 | |
32 | @smyatkin_maxim | 6.5664409995079 сек. | 123 | |
33 | @azhi | 6.9450110197067 сек. | 145 | |
34 | @Valmount |
7.2953402400017 сек. | 147 | |
35 | @Alick09 |
7.4088390469551 сек. | 125 | |
36 | @alexeibs | 7.6391640305519 сек. | 177 | |
37 | @DoctorStein |
7.6435596942902 сек. | 128 | |
38 | @Kenny_HORROR |
7.8451775312424 сек. | 77 | |
39 | @Ratio2 |
7.8529967665672 сек. | 53 | |
40 | @No username specified | 8.0461687445641 сек. | 80 | |
41 | @mobi |
8.129643201828 сек. | 64 | |
42 | @Lonsdaleite |
8.2785065174103 сек. | 92 | |
43 | @tiirz | 8.3757525086403 сек. | 134 | |
44 | @Goryn | 8.3831282258034 сек. | 167 | |
45 | @Leronxp |
8.5381667613983 сек. | 93 | |
46 | @singstio | Да | 8.5835777521133 сек. | 165 |
47 | @CTAKAH4uK |
8.7342492341995 сек. | 173 | |
48 | @XMypuK |
8.8221767544746 сек. | 95 | |
49 | @Edelweiss |
8.8413127660751 сек. | 61 | |
50 | @Jovfer |
9.6698319911957 сек. | 174 | |
51 | @crimaniak |
10.019654750824 сек. | 113 | |
52 | @luckman |
10.166677713394 сек. | 46 | |
53 | @ladilova |
10.607916533947 сек. | 59 | |
54 | @Gromilo |
11.256841778755 сек. | 86 | |
55 | @FreeCoder |
11.380919516087 сек. | 44 | |
56 | @awa |
11.482711791992 сек. | 102 | |
57 | @sprosin |
11.626729488373 сек. | 76 | |
58 | @BelerafonL |
11.740502238274 сек. | 15 | |
59 | @polar_winter |
11.798308491707 сек. | 47 | |
60 | @luckychess |
11.956114530563 сек. | 143 | |
61 | @darinflar | 11.991075217724 сек. | 105 | |
62 | @kreep |
12.082272768021 сек. | 170 | |
63 | @iqmaker | 12.346569001675 сек. | 34 | |
64 | @dima11221122 | 12.357870519161 сек. | 54 | |
65 | @kos66 | 12.412921786308 сек. | 68 | |
66 | @alex_r |
12.501110970974 сек. | 31 | |
67 | @dannk | 12.711302280426 сек. | 138 | |
68 | @andreybotanic |
12.847037494183 сек. | 40 | |
69 | @realsugar | 14.033301234245 сек. | 10 | |
70 | @kromych | 14.101772785187 сек. | 25 | |
71 | @iamnp |
14.298875749111 сек. | 32 | |
72 | @skripkakos |
14.305522501469 сек. | 96 | |
73 | @OnScript |
14.555817246437 сек. | 142 | |
74 | @aserty | 15.127694249153 сек. | 175 | |
75 | @ivanbl4 |
15.24883300066 сек. | 148 | |
76 | @kinbote | 16.56739872694 сек. | 130 | |
77 | @ryokuyou |
16.733837723732 сек. | 106 | |
77.5 | @MarvinPA | 21.251857995987 сек. | 186 | |
78 | @quarck | 21.369844019413 сек. | 157 | |
79 | @sultanko |
21.440900743008 сек. | 172 | |
80 | @Yura1111 |
22.057671248913 сек. | 30 | |
81 | @Troyal |
22.184078454971 сек. | 99 | |
82 | @Izobara |
23.361551761627 сек. | 16 | |
83 | @PutPixel |
35.820213794708 сек. | 180 | |
84 | @CheshaNeko | 53.085104465485 сек. | 120 | |
85 | @fromnull | 53.490429997444 сек. | 65 | |
86 | @ronsenval |
Неверный ответ на сложных тестах | 14 | |
87 | @undiabler |
Неверный ответ на сложных тестах | 26 | |
88 | @MrDindows |
Неверный ответ на сложных тестах | 52 | |
89 | @kladov | Неверный ответ на сложных тестах | 66 | |
90 | @Andrew146 |
Неверный ответ на сложных тестах | 127 | |
91 | @vaux |
Превышено допустимое время на сложных тестах | 22 | |
92 | @marsencpp |
Превышено допустимое время на сложных тестах | 27 | |
93 | @phrk | Превышено допустимое время на сложных тестах | 43 | |
94 | @burtsev | Превышено допустимое время на сложных тестах | 55 | |
95 | @yooll |
Превышено допустимое время на сложных тестах | 58 | |
96 | @DarkContact |
Превышено допустимое время на сложных тестах | 70 | |
97 | @drongosar |
Превышено допустимое время на сложных тестах | 87 | |
98 | @alexvab |
Превышено допустимое время на сложных тестах | 90 | |
99 | @MrKonshyn |
Превышено допустимое время на сложных тестах | 91 | |
100 | @appplemac | Превышено допустимое время на сложных тестах | 112 | |
101 | @msn92 |
Превышено допустимое время на сложных тестах | 136 | |
102 | @ikalnitsky |
Превышено допустимое время на сложных тестах | 152 | |
103 | @0Chekhov0 | Неверный ответ на простых тестах | 1 | |
104 | @savik1 |
Неверный ответ на простых тестах | 2 | |
105 | @zenden2k |
Неверный ответ на простых тестах | 12 | |
106 | @alexaol | Неверный ответ на простых тестах | 17 | |
107 | @Avitella | Неверный ответ на простых тестах | 18 | |
108 | @yrik04 |
Неверный ответ на простых тестах | 24 | |
109 | @topz |
Неверный ответ на простых тестах | 35 | |
110 | @drozdVadym |
Неверный ответ на простых тестах | 37 | |
111 | @anton280 |
Неверный ответ на простых тестах | 39 | |
112 | @ehead01 |
Неверный ответ на простых тестах | 49 | |
113 | @8086 |
Неверный ответ на простых тестах | 50 | |
114 | @DIMKAAAAA |
Неверный ответ на простых тестах | 57 | |
115 | @mike_4d |
Неверный ответ на простых тестах | 60 | |
116 | @alineman | Неверный ответ на простых тестах | 74 | |
117 | @pavor84 | Неверный ответ на простых тестах | 75 | |
118 | @denzp |
Неверный ответ на простых тестах | 79 | |
119 | @RamTararam |
Неверный ответ на простых тестах | 81 | |
120 | @DezzK |
Неверный ответ на простых тестах | 82 | |
121 | @frozendog | Неверный ответ на простых тестах | 83 | |
122 | @sasha237 |
Неверный ответ на простых тестах | 98 | |
123 | @aX1v |
Неверный ответ на простых тестах | 103 | |
124 | @rutigl |
Неверный ответ на простых тестах | 104 | |
125 | @Joric | Неверный ответ на простых тестах | 107 | |
126 | @LibertyPaul |
Неверный ответ на простых тестах | 110 | |
127 | @volokitinss |
Неверный ответ на простых тестах | 111 | |
128 | @Formicidae |
Неверный ответ на простых тестах | 115 | |
129 | @fao |
Неверный ответ на простых тестах | 117 | |
130 | @vkm |
Неверный ответ на простых тестах | 124 | |
131 | @kleninz | Неверный ответ на простых тестах | 131 | |
132 | @knstqq | Неверный ответ на простых тестах | 135 | |
133 | @ryokuyou |
Неверный ответ на простых тестах | 139 | |
134 | @morphing | Неверный ответ на простых тестах | 140 | |
135 | @Vaddddd | Неверный ответ на простых тестах | 144 | |
136 | @ancalled | Неверный ответ на простых тестах | 150 | |
137 | @fasterthanlight | Неверный ответ на простых тестах | 154 | |
138 | @sinc |
Неверный ответ на простых тестах | 155 | |
139 | @Satayev | Неверный ответ на простых тестах | 159 | |
140 | @eversyt |
Неверный ответ на простых тестах | 162 | |
141 | @zyss |
Неверный ответ на простых тестах | 163 | |
142 | @smile616 | Неверный ответ на простых тестах | 166 | |
143 | @Moress |
Неверный ответ на простых тестах | 169 | |
144 | @zzzeeerrr0 |
Неверный ответ на простых тестах | 176 | |
145 | @kilotaras |
Неверный ответ на простых тестах | 182 | |
146 | @I_AM_FAKE |
Превышено допустимое время на простых тестах | 7 | |
147 | @Aksiom |
Превышено допустимое время на простых тестах | 28 | |
148 | @WarAngel_alk |
Превышено допустимое время на простых тестах | 63 | |
149 | @skovpen | Превышено допустимое время на простых тестах | 132 | |
150 | @safinaskar | Превышено допустимое время на простых тестах | 160 | |
151 | @No username specified | Превышено допустимое время на простых тестах | 168 | |
152 | @jit_md |
Превышено допустимое время на простых тестах | 181 | |
153 | @mrigi | Попытка работать с отсутствующей сетью | 146 | |
154 | @Tweekaz |
Ошибка компиляции | 3 | |
155 | @No username specified | Ошибка компиляции | 4 | |
156 | @Thunderbird |
Ошибка компиляции | 9 | |
157 | @shock_one |
Ошибка компиляции | 13 | |
158 | @shy | Ошибка компиляции | 23 | |
159 | @Dgut | Ошибка компиляции | 38 | |
160 | @ShouldNotSeeMe |
Ошибка компиляции | 56 | |
161 | @therussianphysicist |
Ошибка компиляции | 62 | |
162 | @aamuvirkku |
Ошибка компиляции | 84 | |
163 | @IntegralUnderground |
Ошибка компиляции | 85 | |
164 | @0leksandr |
Ошибка компиляции | 88 | |
165 | @ipoder |
Ошибка компиляции | 94 | |
166 | @IharBury |
Ошибка компиляции | 97 | |
167 | @xtern |
Ошибка компиляции | 100 | |
168 | @KycokCo6aku |
Ошибка компиляции | 101 | |
169 | @gridem | Ошибка компиляции | 118 | |
170 | @minc2319 |
Ошибка компиляции | 141 | |
171 | @okneigres | Ошибка компиляции | 151 | |
172 | @antidotcb |
Ошибка компиляции | 164 | |
173 | @merkius | Превышен допустимый размер файла | 71 | |
174 | @iTwin |
Превышен допустимый размер файла | 29 | |
175 | @bstructure | Превышен допустимый размер файла | 153 | |
176 | @fsv |
Превышен допустимый размер файла | 51 | |
177 | @411 |
Превышен допустимый размер файла | 72 | |
178 | @pleha | Превышен допустимый размер файла | 67 | |
179 | @staricam |
Превышен допустимый размер файла | 73 | |
180 | @chipa | Превышен допустимый размер файла | 119 | |
181 | @dosefose | Превышен допустимый размер файла | 121 | |
182 | @SergeySib |
Превышен допустимый размер файла | 161 | |
183 | @Ptax | Превышен допустимый размер файла | 137 |
Вне конкурса
Решения присланные после дедлайна:№ | Habraname | Нужен ли инвайт | Результат | System ID |
---|---|---|---|---|
1 | @bstructure | 1.5542407631874 сек. | 192 | |
2 | @corsairnv |
12.768928468227 сек. | 194 | |
3 | @theirbaldness | 15.648555219173 сек. | 191 | |
4 | @pavor84 | Неверный ответ на простых тестах | 189 | |
5 | @Jamim |
Неверный ответ на простых тестах | 193 | |
6 | @1dash | Ошибка компиляции | 188 |
Об ошибках
Писали для MS VC: __int64 вместо long long или __int64_t, не подключен math.h, использование отсутствующего stdafx.h.Писали для Windows: Math.h<>math.h
Bleeding-edge C++11 фичи: К сожалению, корректный код не всегда компилируется. У clang есть проблемы с C++11 многопоточностью (компилятор не может скомпилировать стандартную библиотеку, баг известен — я пробовал накатить патч — но не помогло). Если это не протестировать до отправки на целевом компиляторе — то проблему никак не обнаружить.
Синтаксические ошибки: Банальная внимательность — подозреваю отправку не сохраненного файла.
Непортируемый на 64-bit код: Попытки неявно привести указатель к int, и обратно.
memset: undeclared identifier 'memset'; did you mean 'wmemset'? Находилось онлайн-тестом на сайте llvm. Самая популярная ошибка.
C#: Один случай.
Неверный формат комментария с именем пользователя: Решения все равно протестированы, чтобы мучились теперь где-чьё :-).
Segmentation fault: Половина неверных ответов на коротких тестах — это segfault-ы и краши.
Увидеть свои результаты компиляции можно тут (смотреть по System ID).
Полный архив исходных текстов решений.
Решения
Изначально я хотел рассказать и об алгоритмах решения — но сейчас я вижу, что понятия не имею, как работают первые 2 места, потому лучше нам подождать авторов :-) Тем не менее, стоит заметить, что использование потоков не является необходимым условием для победы.Shadeware, победитель
@shadeware У вас ничего не глючит, это компилируется.
//@shadeware
#include <cstdio>
#include <vector>
#include <cmath>
unsigned i,n,Q,j,L;long long u[66],A;int main(){for(;i<448;i++)u[i/7+2]=u[i/7+2]*96+"+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL0"
"5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i]-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u[i];scanf("%u",&n);Q=sqrt(n)+1e-7,L=n>>24<<24;A=u[(n>>24)+1]+2*!L*!!~-n;std::vector<bool>S(Q/2+1),B(n-L+2);B[1]=!L;for(i=3;i<=Q;i+=2)if(!S[i/2]){for(j=3*i;j<=Q;j+=2*i)S[j/2]=1;for(j=L?(L+i-1)/i*i:2*i;j<=n;j+=i)B[j-L]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llu\n",A);}
Mikhaelkh, 2-е место
@mikhaelkh Компилятор ругался на текстовую строку — но все скомпилировалось.
//@mikhaelkh
#include <cstdio>
#include <bitset>
unsigned char s[]=" 3ћfСЫБ b”Ђ)Cр —іЈ€Я $9шэD » $ѕ|Іш† %ЃЉЃмF &_яВГЕЕ 'Y¶FьВµ (nsџИp± )ќлznQ2 *иSР—ж) ,oшtе\\v -пW0BC† /«Ю#)ґ 1‚ьј”8P 3sю[Y6i 5.qЛ.“ 7¤zMЃшj 9г—‹XyЇ <_‰XжЅ >ТOh«€Y AЃМ“«n DKr]µrЩ G.?“нU J*Ј»‚Џ M@Eп†Ь PpYґпHј S№pvdјя W>дGpІш ZєQЦаЋ~ ^qяmty= bC†,щnт f.d“¤ ¤ j1Ж [|Ј nN№BўЮ: r…ЄGрр vФiчwЁ{ {_Лз}Lh б*sЁЭ# „ћoї‹УE ‰to]¶е~ Ћd*4:иХ “kѕK8ћш Њ~ќQЄ ќЕЛ7д6« Ј;Ёл0ўь Ё§Iвc§б ObЗюЏP імЏxь>† №Е›»ЯPo ї·NцбЬ† ЕБ1ґgп& ЛгlъІcѓ ТAdЎ“[$ Ш–Й:ілЧ Я%юі±Ю1 е«_7бќЌ мlчnєСџ уF”ЭDРЭ ъ8ћуcћЖ $$CМжМMЕ $+gDbцPр $2ЎЧтУ‡E $9цАП†Ы ";
enum{S=1<<14,N=1<<23};
long long a[65],res;
std::bitset<S> u;
std::bitset<N> v;
int n,r,x,i,j;
int main() {
scanf("%d",&n);
for (i=1;i<65;++i)
for (++j;s[j]>32;++j)
a[i]=221*a[i]+s[j]-35;
*a=2,res=a[j=n/2/N],x=j*2*N,v[0]=!j;
for (i=3;i<S+S;i+=2)
if (!u[i/2]) {
for (j=i*i/2;j<S;j+=i)u[j]=1;
for (j=(x?((r=i-x%i)&1?r:r+i):i*i)/2;j<N;j+=i)v[j]=1;
}
for(i=1;i<=n-x;i+=2)
if(!v[i/2])res+=x+i;
printf("%lld\n", n>1?res:0);
}
Icemore, 3-е место, самое быстрое многопоточное решение
@Icemore
//@Icemore
#include<iostream>
#include<cmath>
#include<memory.h>
#include<pthread.h>
#define lng long long
const int T=4,Q=33000,S=100000;
bool np[Q],b[T][S];
int p[Q],c,B,s,e;
lng A[T],R,P[]={0,1906816620981654LL,7357074544482779LL,16217881619242062LL,28422918403819825LL};
void* f(void*_){
long id=(long)_;
int C=(e/S-B+1)/T,q,M,i,j,k;
M=(id==T-1)?(e/S+1):(id+1)*C+B;
for(k=id*C+B;k<M;++k){
memset(b[id],0,sizeof(bool)*S);q=k*S;
for(i=0;i<c;++i){
j=(q+p[i]-1)/p[i];j=(j>1?j:2)*p[i]-q;
for(;j<S;j+=p[i])b[id][j]=1;
}
if(!k)b[id][0]=b[id][1]=1;
for(i=std::max(0,s-q);i<S&&q+i<=e;++i)if(!b[id][i])A[id]+=q+i;
}
return 0;
}
int main(){
int n,i,q,j;
std::cin>>n;
i=(n-1)/(1<<28);s=i*(1<<28)+2;e=(i+1)*(1<<28);
if(n-s-1<e-n)R=P[i],e=n;else s=n+1,R=-P[i+1];
B=s/S;q=(int)sqrt(e+.0);p[c++]=2;
for(i=3;i<=q;i+=2)if(!np[i])for(j=i*i,p[c++]=i;j<=q;j+=i)np[j]=1;
pthread_t t[T];
for(i=0;i<T;++i)pthread_create(t+i,0,f,(void*)(i));
for(i=0;i<T;++i)pthread_join(t[i],0),R+=A[i];
std::cout<<(R>0?R:-R);
}
ripatti, 4-е место
@ripatti
//@ripatti
//идея - блочное решето с предпросчетом ответов для нескольких первых блоков
#include <iostream>
#include <memory.h>
#define S 150000
bool F[40000],B[S];
int P[10000],p=0;
long long pre[]={0,79835127420606,307011790722811,675490692294675,
1182357709860117,1825666731904492,2603717273255596,3515373254256955,
4559774703609068,5736228298250417,7043215380181465,8481171232603598,
10049045128993920,11745741297705187,13571569117886223,15525668198679060,
17608378509778587,19817357312226874,22154562782502270,24618987306923167,
27209541722648039};
int main(){
int a,b,c,n,Z=(1<<15),Q=S*350;
std::cin >> n;
long long ans=pre[n/Q];
for(a=2;a*a<Z;a++)if(!F[a])for(b=a*a;b<Z;b+=a)F[b]=true;
for(a=2;a<Z;a++)if(!F[a])P[p++]=a;
for(a=(n/Q)*Q;a<=n;a+=S){
memset(B,0,sizeof B);
for(b=0;b<p;b++)for(c=std::max(2,(a+P[b]-1)/P[b])*P[b]-a;c<S;c+=P[b])B[c]=true;
if(a==0)B[0]=B[1]=true;
for(b=0;b<S&&a+b<=n;b++)if(!B[b])ans+=a+b;
}
std::cout << ans;
return 0;
}
kbxxi, 5-е место
@kbxxi
//@kbxxi
#include <iostream>
long long A[]={0,72619548630277,279209790387276,614333144695291,1075207199997334,1660170771905893,2367646772295462,
3196703482711201,4146437503168147,5215984059716389,6404774487532576,7711724083073573,9137303389808024,
10680189372387880,12340337443955708,14116726304047228,16010026481858292,18019518580817005,20143329357815162,
22383876593236984,24739512092254535,27209541722648039};
char S[50000100];
int p[50100],C,i,j,B=50000000,l,r;
long long R=0;
int main(){
std::cin >> r;
for (i=2;i<=100000;i++)
if (!S[i]){
p[C++]=i;
for (j=2*i;j<=100000;j+=i)
S[j]=1;
} else S[i]=0;
l=r/B*B+1;
for (i=1;p[i]*p[i]<=r;i++){
int v=p[i],P=l/v*v;
if (P<l) P+=v;
if (P==v) P+=v;
if (!(P&1)) P+=v;
v*=2;
while (P<=r) S[P-l]=1,P+=v;
}
for (i=l;i<=r;i+=2) if (!S[i-l] && i!=1) R+=i;
if (l==1 && r>1) R+=2;
std::cout<<A[r/B]+R;
return 0;
}
Singstio, самое короткое решение проходящее все тесты
@singstio 304 байта, никакого «сжатия»
//@singstio
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main()
{
__int64_t n,sum=0,i,j,sn;
cin>>n;
sn=int(sqrt(n))+1;
vector<bool> s(n+1,true);
for(i=2;i<=sn;i++)
if(s[i]){
for(j=i*i;j<=n;j+=i)s[j]=false;}
for(i=2;i<=n;i++)if(s[i])sum+=i;
cout<<sum<<endl;
}
Мораль
- Сначала правильный алгоритм, потом многопоточность.
- Перенос C++ программ на другую ОС, разрядность, компилятор — сложный и тернистый путь, тестировать на целевой платформе нужно обязательно. Вдвойне это касается bleeding-edge фич.
О моих ошибках
Вам кажется что у вас все работает, а в таблице — что-то неправильное?Рекомендую взять отправленное вами решение _из архива с решениями_, и скомпилировать на clang 3.2 64bit — и если заработает — тогда писать мне. Уже человек 10 написали, что у них все работает, а проблема всегда была или в другом компиляторе или во внимательности.
Only registered users can participate in poll. Log in, please.
Стоит ли организовать следующее хабра-соревнование через 3-6 месяцев, только с онлайн-приемом решений и проверкой на компилируемость не отходя от кассы?
7.29% Нет уж, и так весь новый год испортил… К тому же, всегда есть USACO, TopCoder…130
94.23% Пожалуй да!1681
1784 users voted. 390 users abstained.