Honestly, I did not expect such a number of solutions: 265 solutions were sent in 24 hours, of which

183 were left after the removal of the resubmission. Out of 183 solutions, 11 exceeded the allowed solution size, in 19 cases it was not possible to compile (more about these errors below). Then 47 gave incorrect answers on simple tests (1..1000000), 8 did not have time to calculate the answer per minute (the sample solution from the problem statement for 1 million worked 5 minutes 36 seconds).

On complex tests - 5 solutions gave the wrong answer, and 12 - did not fit in one minute. 86 - successfully passed all the tests.

If anyone lost, here is a topic about starting a competition with the conditions of the problem .

About tests and testing

Everything was tested with commonplace scripts, the most time-consuming operation is to save solutions from the mail with your hands (and repeated file names ... 42 pieces of main.cpp ....). This is probably one of those cases when writing a web application for making decisions is faster than scooping up tons of mail. Testing results - added up in MySQL, from where the results table was built.

Simple tests:

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");

Complex tests:
Averaged runtime was estimated (i.e. runtime for 4 different input values ​​divided by 4). The 3 fastest solutions were tested with 100-fold repetition - to get a more accurate runtime (unlike a single run within 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);

Result table

Colleagues, click on invites:

No.	Habraname	Do I need an invite?	Result	System id
1	@shadeware	Not anymore	0.035053772330284 sec.	48
2	@mikhaelkh	Not anymore	0.039169362783432 sec	41
3	@Icemore	Not anymore	0.068273649811745 sec	129
4	@ripatti	Not anymore	0.11206769943237 sec.	8
5	@kbxxi	Not anymore	0.15401327610016 sec.	156
6	@monoid	Not anymore	0.22840601205826 sec.	69
7	@ Zver1992		0.23262423276901 sec.	133
8	@Mrrl		0.37099504470825 sec.	178
9	@Staker	Yes	0.66007524728775 sec.	171
10	@SyDr	Yes	0.93328875303268 sec.	78
eleven	@vbarinov	Yes	3.2648342847824 sec	108
12	@vanla	Yes	3.3831697702408 sec.	19
thirteen	@MaSaK	Yes	3.4151287674904 sec.	20
14	@ dark1ight		3.5476635098457 sec.	36
fifteen	@udalov	Yes	3.8905065059662 sec.	116
16	@bklim		4.3489827513695 sec.	149
17	@cfighter		4.4272682070732 sec.	eleven
18	@VladVR		4.7588297724724 sec.	89
19	@borozdinKirill		4.775633752346 sec.	109
20	@ZhekSooN		4.8941134810448 sec.	122
21	@madkite		4.9126330018044 sec.	114
22	@akazakow		5.208831012249 sec.	45
23	@mingrief		5.2523249983788 sec.	179
24	@pasky		5.9874464869499 sec.	5
25	@ ewnd9		6.024626493454 sec	183
26	@gnhdnb		6.0333037376404 sec.	158
27	@through_horizon		6.2488570213318 sec.	21
28	@ kosmos89		6.2885909676552 sec.	126
29th	@Nickel		6.36874127388 sec.	42
thirty	@infsega		6.4502172470093 sec.	33
31	@shuternay		6.4606020450592 sec.	6
32	@smyatkin_maxim		6.5664409995079 sec	123
33	@azhi		6.9450110197067 sec.	145
34	@Valmount		7.2953402400017 sec.	147
35	@ Alick09		7.4088390469551 sec.	125
36	@alexeibs		7.6391640305519 sec.	177
37	@DoctorStein		7.6435596942902 sec.	128
38	@Kenny_HORROR		7.8451775312424 sec.	77
39	@ Ratio2		7.8529967665672 sec.	53
40	@No username specified		8.0461687445641 sec.	80
41	@mobi		8.129643201828 sec.	64
42	@Lonsdaleite		8.2785065174103 sec.	92
43	@tiirz		8.3757525086403 sec.	134
44	@Goryn		8.3831282258034 sec.	167
45	@Leronxp		8.5381667613983 sec.	93
46	@singstio	Yes	8.5835777521133 sec.	165
47	@ CTAKAH4uK		8.7342492341995 sec.	173
48	@XMypuK		8.8221767544746 sec.	95
49	@Edelweiss		8.8413127660751 sec.	61
fifty	@Jovfer		9.6698319911957 seconds	174
51	@crimaniak		10.019654750824 sec.	113
52	@luckman		10.166677713394 seconds	46
53	@ladilova		10.607916533947 sec.	59
54	@Gromilo		11.256841778755 sec.	86
55	@FreeCoder		11.380919516087 sec.	44
56	@awa		11.482711791992 sec.	102
57	@sprosin		11.626729488373 sec.	76
58	@BelerafonL		11.740502238274 sec.	fifteen
59	@polar_winter		11.798308491707 seconds	47
60	@luckychess		11.956114530563 sec.	143
61	@darinflar		11.991075217724 sec.	105
62	@kreep		12.082272768021 sec.	170
63	@iqmaker		12.346569001675 sec.	34
64	@ dima11221122		12.357870519161 sec.	54
65	@ kos66		12.412921786308 sec.	68
66	@alex_r		12.501110970974 sec.	31
67	@dannk		12.711302280426 sec.	138
68	@andreybotanic		12.847037494183 sec.	40
69	@realsugar		14.033301234245 sec.	10
70	@kromych		14.101772785187 sec.	25
71	@iamnp		14.298875749111 sec.	32
72	@skripkakos		14.305522501469 sec.	96
73	@OnScript		14.555817246437 sec.	142
74	@aserty		15.127694249153 sec.	175
75	@ ivanbl4		15.24883300066 sec.	148
76	@kinbote		16.56739872694 sec.	130
77	@ryokuyou		16.7338377232332 sec.	106
77.5	@MarvinPA		21.251857995987 sec.	186
78	@quarck		21.369844019413 sec.	157
79	@sultanko		21.440900743008 seconds	172
80	@ Yura1111		22.057671248913 sec.	thirty
81	@Troyal		22.184078454971 sec.	99
82	@Izobara		23.361551761627 sec.	16
83	@PutPixel		35.820213794708 sec.	180
84	@CheshaNeko		53.085104465485 sec.	120
85	@fromnull		53.490429997444 sec.	65
86	@ronsenval		Wrong answer on complex tests	14
87	@undiabler		Wrong answer on complex tests	26
88	@MrDindows		Wrong answer on complex tests	52
89	@kladov		Wrong answer on complex tests	66
90	@ Andrew146		Wrong answer on complex tests	127
91	@vaux		Exceeded time limit for difficult tests	22
92	@marsencpp		Exceeded time limit for difficult tests	27
93	@phrk		Exceeded time limit for difficult tests	43
94	@burtsev		Exceeded time limit for difficult tests	55
95	@yooll		Exceeded time limit for difficult tests	58
96	@DarkContact		Exceeded time limit for difficult tests	70
97	@drongosar		Exceeded time limit for difficult tests	87
98	@alexvab		Exceeded time limit for difficult tests	90
99	@MrKonshyn		Exceeded time limit for difficult tests	91
100	@appplemac		Exceeded time limit for difficult tests	112
101	@ msn92		Exceeded time limit for difficult tests	136
102	@ikalnitsky		Exceeded time limit for difficult tests	152
103	@ 0Chekhov0		Invalid answer on simple tests.	1
104	@ savik1		Invalid answer on simple tests.	2
105	@ zenden2k		Invalid answer on simple tests.	12
106	@alexaol		Invalid answer on simple tests.	17
107	@Avitella		Invalid answer on simple tests.	18
108	@ yrik04		Invalid answer on simple tests.	24
109	@topz		Invalid answer on simple tests.	35
110	@drozdVadym		Invalid answer on simple tests.	37
111	@ anton280		Invalid answer on simple tests.	39
112	@ ehead01		Invalid answer on simple tests.	49
113	@ 8086		Invalid answer on simple tests.	fifty
114	@DIMKAAAAA		Invalid answer on simple tests.	57
115	@ mike_4d		Invalid answer on simple tests.	60
116	@alineman		Invalid answer on simple tests.	74
117	@ pavor84		Invalid answer on simple tests.	75
118	@denzp		Invalid answer on simple tests.	79
119	@RamTararam		Invalid answer on simple tests.	81
120	@DezzK		Invalid answer on simple tests.	82
121	@frozendog		Invalid answer on simple tests.	83
122	@ sasha237		Invalid answer on simple tests.	98
123	@ aX1v		Invalid answer on simple tests.	103
124	@rutigl		Invalid answer on simple tests.	104
125	@Joric		Invalid answer on simple tests.	107
126	@LibertyPaul		Invalid answer on simple tests.	110
127	@volokitinss		Invalid answer on simple tests.	111
128	@Formicidae		Invalid answer on simple tests.	115
129	@fao		Invalid answer on simple tests.	117
130	@vkm		Invalid answer on simple tests.	124
131	@kleninz		Invalid answer on simple tests.	131
132	@knstqq		Invalid answer on simple tests.	135
133	@ryokuyou		Invalid answer on simple tests.	139
134	@morphing		Invalid answer on simple tests.	140
135	@Vaddddd		Invalid answer on simple tests.	144
136	@ancalled		Invalid answer on simple tests.	150
137	@fasterthanlight		Invalid answer on simple tests.	154
138	@sinc		Invalid answer on simple tests.	155
139	@Satayev		Invalid answer on simple tests.	159
140	@eversyt		Invalid answer on simple tests.	162
141	@zyss		Invalid answer on simple tests.	163
142	@ smile616		Invalid answer on simple tests.	166
143	@Moress		Invalid answer on simple tests.	169
144	@ zzzeeerrr0		Invalid answer on simple tests.	176
145	@kilotaras		Invalid answer on simple tests.	182
146	@I_AM_FAKE		Exceeded time limits on simple tests	7
147	@Aksiom		Exceeded time limits on simple tests	28
148	@WarAngel_alk		Exceeded time limits on simple tests	63
149	@skovpen		Exceeded time limits on simple tests	132
150	@safinaskar		Exceeded time limits on simple tests	160
151	@No username specified		Exceeded time limits on simple tests	168
152	@jit_md		Exceeded time limits on simple tests	181
153	@mrigi		Trying to work with a missing network	146
154	@Tweekaz		Compilation error	3
155	@No username specified		Compilation error	4
156	@Thunderbird		Compilation error	9
157	@shock_one		Compilation error	thirteen
158	@shy		Compilation error	23
159	@Dgut		Compilation error	38
160	@ShouldNotSeeMe		Compilation error	56
161	@therussianphysicist		Compilation error	62
162	@aamuvirkku		Compilation error	84
163	@IntegralUnderground		Compilation error	85
164	@ 0leksandr		Compilation error	88
165	@ipoder		Compilation error	94
166	@IharBury		Compilation error	97
167	@xtern		Compilation error	100
168	@ KycokCo6aku		Compilation error	101
169	@gridem		Compilation error	118
170	@ minc2319		Compilation error	141
171	@okneigres		Compilation error	151
172	@antidotcb		Compilation error	164
173	@merkius		File size exceeded	71
174	@iTwin		File size exceeded	29th
175	@bstructure		File size exceeded	153
176	@fsv		File size exceeded	51
177	@ 411		File size exceeded	72
178	@pleha		File size exceeded	67
179	@staricam		File size exceeded	73
180	@chipa		File size exceeded	119
181	@dosefose		File size exceeded	121
182	@SergeySib		File size exceeded	161
183	@Ptax		File size exceeded	137

Out of competition

Decisions sent after deadline:

No.	Habraname	Do I need an invite?	Result	System id
1	@bstructure		1.5542407631874 sec.	192
2	@corsairnv		12.768928468227 sec.	194
3	@theirbaldness		15.648555219173 sec.	191
4	@ pavor84		Invalid answer on simple tests.	189
5	@Jamim		Invalid answer on simple tests.	193
6	@ 1dash		Compilation error	188

About bugs

They wrote for MS VC : __int64 instead of long long or __int64_t, math.h is not connected, using the missing stdafx.h.
They wrote for Windows : Math.h <> math.h
Bleeding-edge C ++ 11 features : Unfortunately, the correct code does not always compile. Clang has problems with C ++ 11 multithreading (the compiler cannot compile the standard library, the bug is known - I tried rolling the patch - but it didn’t help). If this is not tested before sending to the target compiler, then there is no way to detect the problem.
Syntax errors : Banal care - I suspect sending an unsaved file.
64-bit non-portable code : Attempts to implicitly cast a pointer to an int, and vice versa.
memset: undeclared identifier 'memset'; did you mean 'wmemset'? It was an online test on the llvm website. The most popular mistake.
C # : One case.
Incorrect comment format with username : Solutions are still tested, so now they’re tormented somewhere :-).
Segmentation fault : Half of the incorrect answers in the short tests are segfaults and crashes.

You can see your compilation results here (see System ID).
A complete archive of source code solutions .

Solutions

Initially, I wanted to talk about decision algorithms - but now I see that I have no idea how the first 2 places work, so it's better for us to wait for the authors :-) Nevertheless, it is worth noting that the use of threads is not a necessary condition for victory.

Singstio, самое короткое решение проходящее все тесты

@singstio 304 байта, никакого «сжатия»

//@singstio
#include
#include
#include
using namespace std;
int main()
{
  __int64_t n,sum=0,i,j,sn;
  cin>>n;
  sn=int(sqrt(n))+1;
  vector 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<

Мораль

• Сначала правильный алгоритм, потом многопоточность.
• Перенос C++ программ на другую ОС, разрядность, компилятор — сложный и тернистый путь, тестировать на целевой платформе нужно обязательно. Вдвойне это касается bleeding-edge фич.

О моих ошибках

Вам кажется что у вас все работает, а в таблице — что-то неправильное?
Рекомендую взять отправленное вами решение _из архива с решениями_, и скомпилировать на clang 3.2 64bit — и если заработает — тогда писать мне. Уже человек 10 написали, что у них все работает, а проблема всегда была или в другом компиляторе или во внимательности.