简单的测试题3

概述

简单的测试题3是完整的NOIp Senior,分2天,目前只有PDF版本的题目,所有文件在https://github.com/zhzh2001/Learning-public/tree/master/test上公开。

另外,借助pdf2htmlEX,题目和题解转为HTML版本:

可以尝试在这里提交:fact core_region

被移除的题目

2.最近点对(pair.cpp/c/pas)

题目描述

二维平面上有N个点(2N200,0002\le N\le200,000),编号1N1\ldots N。两点之间的距离为欧几里得距离,即disti,j=(xixj)2+(yiyj)2dist_{i,j}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}

现在请求出所有点对中,距离最小的点对间的距离的平方

输入格式(pair.in)

第一行一个整数N

接下来N行,每行两个整数xi,yix_i,y_i(0xi,yi1,000,000,0000\le x_i,y_i\le1,000,000,000)

输出格式(pair.out)

一个整数表示最近点对间距离的平方

输入样例

1
2
3
4
5
4
0 0
2 1
1 3
3 5

输出样例

1
5

样例解释

最近的点对是(1,2)和(2,3),距离的平方为12+22=51^2+2^2=5

数据范围

本题打包测试,必须通过一个子任务中的所有测试点才能得到对应的分值。

  • subtask1(30%):N5,000N\le5,000
  • subtask2(30%):N50,000N\le50,000
  • subtask3(20%):N200,0000xi,yi1,000N\le200,000\;\;0\le x_i,y_i\le1,000
  • subtask4(20%):N200,000N\le200,000

对于100%的数据,N200,0000xi,yi1,000,000,000N\le200,000\;\;0\le x_i,y_i\le1,000,000,000

标程

day1

fact.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
#include<fstream>
#include<string>
#include<sstream>
using namespace std;

__float128 lgammaq (__float128);
__float128 logq (__float128);
__float128 powq (__float128, __float128);
__float128 scalbnq (__float128, int);

#define M_LN10q 2.3025850929940456840179914546843642Q /* log_e 10 */

/* Main union type we use to manipulate the floating-point type. */
typedef union
{
__float128 value;

struct
{
unsigned long long mant_low:64;
unsigned long long mant_high:48;
unsigned exponent:15;
unsigned negative:1;
} ieee;

struct
{
unsigned long long low;
unsigned long long high;
} words64;

struct
{
unsigned w3;
unsigned w2;
unsigned w1;
unsigned w0;
} words32;

struct
{
unsigned long long mant_low:64;
unsigned long long mant_high:47;
unsigned quiet_nan:1;
unsigned exponent:15;
unsigned negative:1;
} nan;

} ieee854_float128;


/* Get two 64 bit ints from a long double. */
#define GET_FLT128_WORDS64(ix0,ix1,d) \
do { \
ieee854_float128 u; \
u.value = (d); \
(ix0) = u.words64.high; \
(ix1) = u.words64.low; \
} while (0)

/* Get the more significant 64 bits of a long double mantissa. */
#define GET_FLT128_MSW64(v,d) \
do { \
ieee854_float128 u; \
u.value = (d); \
(v) = u.words64.high; \
} while (0)

/* Set the more significant 64 bits of a long double mantissa from an int. */
#define SET_FLT128_MSW64(d,v) \
do { \
ieee854_float128 u; \
u.value = (d); \
u.words64.high = (v); \
(d) = u.value; \
} while (0)

static const __float128 one = 1.0Q;
static const __float128 huge = 1.0e4000Q;

/* log gamma(x) = ( x - 0.5 ) * log(x) - x + LS2PI + 1/x P(1/x^2)
1/x <= 0.0741 (x >= 13.495...)
Peak relative error 1.5e-36 */
static const __float128 ls2pi = 9.1893853320467274178032973640561763986140E-1Q;
#define NRASY 12
static const __float128 RASY[NRASY + 1] =
{
8.333333333333333333333333333310437112111E-2Q,
-2.777777777777777777777774789556228296902E-3Q,
7.936507936507936507795933938448586499183E-4Q,
-5.952380952380952041799269756378148574045E-4Q,
8.417508417507928904209891117498524452523E-4Q,
-1.917526917481263997778542329739806086290E-3Q,
6.410256381217852504446848671499409919280E-3Q,
-2.955064066900961649768101034477363301626E-2Q,
1.796402955865634243663453415388336954675E-1Q,
-1.391522089007758553455753477688592767741E0Q,
1.326130089598399157988112385013829305510E1Q,
-1.420412699593782497803472576479997819149E2Q,
1.218058922427762808938869872528846787020E3Q
};


/* Evaluate P[n] x^n + P[n-1] x^(n-1) + ... + P[0] */

static __float128
neval (__float128 x, const __float128 *p, int n)
{
__float128 y;

p += n;
y = *p--;
do
{
y = y * x + *p--;
}
while (--n > 0);
return y;
}


__float128
lgammaq (__float128 x)
{
__float128 p, q;

q = ls2pi - x;
q = (x - 0.5Q) * logq (x) + q;
if (x > 1.0e18Q)
return (q);

p = 1.0Q / (x * x);
q += neval (p, RASY, NRASY) / x;
return (q);
}

/* log(1+x) = x - .5 x^2 + x^3 l(x)
-.0078125 <= x <= +.0078125
peak relative error 1.2e-37 */
static const __float128
l3 = 3.333333333333333333333333333333336096926E-1Q,
l4 = -2.499999999999999999999999999486853077002E-1Q,
l5 = 1.999999999999999999999999998515277861905E-1Q,
l6 = -1.666666666666666666666798448356171665678E-1Q,
l7 = 1.428571428571428571428808945895490721564E-1Q,
l8 = -1.249999999999999987884655626377588149000E-1Q,
l9 = 1.111111111111111093947834982832456459186E-1Q,
l10 = -1.000000000000532974938900317952530453248E-1Q,
l11 = 9.090909090915566247008015301349979892689E-2Q,
l12 = -8.333333211818065121250921925397567745734E-2Q,
l13 = 7.692307559897661630807048686258659316091E-2Q,
l14 = -7.144242754190814657241902218399056829264E-2Q,
l15 = 6.668057591071739754844678883223432347481E-2Q;

/* Lookup table of ln(t) - (t-1)
t = 0.5 + (k+26)/128)
k = 0, ..., 91 */
static const __float128 logtbl[92] = {
-5.5345593589352099112142921677820359632418E-2Q,
-5.2108257402767124761784665198737642086148E-2Q,
-4.8991686870576856279407775480686721935120E-2Q,
-4.5993270766361228596215288742353061431071E-2Q,
-4.3110481649613269682442058976885699556950E-2Q,
-4.0340872319076331310838085093194799765520E-2Q,
-3.7682072451780927439219005993827431503510E-2Q,
-3.5131785416234343803903228503274262719586E-2Q,
-3.2687785249045246292687241862699949178831E-2Q,
-3.0347913785027239068190798397055267411813E-2Q,
-2.8110077931525797884641940838507561326298E-2Q,
-2.5972247078357715036426583294246819637618E-2Q,
-2.3932450635346084858612873953407168217307E-2Q,
-2.1988775689981395152022535153795155900240E-2Q,
-2.0139364778244501615441044267387667496733E-2Q,
-1.8382413762093794819267536615342902718324E-2Q,
-1.6716169807550022358923589720001638093023E-2Q,
-1.5138929457710992616226033183958974965355E-2Q,
-1.3649036795397472900424896523305726435029E-2Q,
-1.2244881690473465543308397998034325468152E-2Q,
-1.0924898127200937840689817557742469105693E-2Q,
-9.6875626072830301572839422532631079809328E-3Q,
-8.5313926245226231463436209313499745894157E-3Q,
-7.4549452072765973384933565912143044991706E-3Q,
-6.4568155251217050991200599386801665681310E-3Q,
-5.5356355563671005131126851708522185605193E-3Q,
-4.6900728132525199028885749289712348829878E-3Q,
-3.9188291218610470766469347968659624282519E-3Q,
-3.2206394539524058873423550293617843896540E-3Q,
-2.5942708080877805657374888909297113032132E-3Q,
-2.0385211375711716729239156839929281289086E-3Q,
-1.5522183228760777967376942769773768850872E-3Q,
-1.1342191863606077520036253234446621373191E-3Q,
-7.8340854719967065861624024730268350459991E-4Q,
-4.9869831458030115699628274852562992756174E-4Q,
-2.7902661731604211834685052867305795169688E-4Q,
-1.2335696813916860754951146082826952093496E-4Q,
-3.0677461025892873184042490943581654591817E-5Q,
0.0000000000000000000000000000000000000000E0Q,
-3.0359557945051052537099938863236321874198E-5Q,
-1.2081346403474584914595395755316412213151E-4Q,
-2.7044071846562177120083903771008342059094E-4Q,
-4.7834133324631162897179240322783590830326E-4Q,
-7.4363569786340080624467487620270965403695E-4Q,
-1.0654639687057968333207323853366578860679E-3Q,
-1.4429854811877171341298062134712230604279E-3Q,
-1.8753781835651574193938679595797367137975E-3Q,
-2.3618380914922506054347222273705859653658E-3Q,
-2.9015787624124743013946600163375853631299E-3Q,
-3.4938307889254087318399313316921940859043E-3Q,
-4.1378413103128673800485306215154712148146E-3Q,
-4.8328735414488877044289435125365629849599E-3Q,
-5.5782063183564351739381962360253116934243E-3Q,
-6.3731336597098858051938306767880719015261E-3Q,
-7.2169643436165454612058905294782949315193E-3Q,
-8.1090214990427641365934846191367315083867E-3Q,
-9.0486422112807274112838713105168375482480E-3Q,
-1.0035177140880864314674126398350812606841E-2Q,
-1.1067990155502102718064936259435676477423E-2Q,
-1.2146457974158024928196575103115488672416E-2Q,
-1.3269969823361415906628825374158424754308E-2Q,
-1.4437927104692837124388550722759686270765E-2Q,
-1.5649743073340777659901053944852735064621E-2Q,
-1.6904842527181702880599758489058031645317E-2Q,
-1.8202661505988007336096407340750378994209E-2Q,
-1.9542647000370545390701192438691126552961E-2Q,
-2.0924256670080119637427928803038530924742E-2Q,
-2.2346958571309108496179613803760727786257E-2Q,
-2.3810230892650362330447187267648486279460E-2Q,
-2.5313561699385640380910474255652501521033E-2Q,
-2.6856448685790244233704909690165496625399E-2Q,
-2.8438398935154170008519274953860128449036E-2Q,
-3.0058928687233090922411781058956589863039E-2Q,
-3.1717563112854831855692484086486099896614E-2Q,
-3.3413836095418743219397234253475252001090E-2Q,
-3.5147290019036555862676702093393332533702E-2Q,
-3.6917475563073933027920505457688955423688E-2Q,
-3.8723951502862058660874073462456610731178E-2Q,
-4.0566284516358241168330505467000838017425E-2Q,
-4.2444048996543693813649967076598766917965E-2Q,
-4.4356826869355401653098777649745233339196E-2Q,
-4.6304207416957323121106944474331029996141E-2Q,
-4.8285787106164123613318093945035804818364E-2Q,
-5.0301169421838218987124461766244507342648E-2Q,
-5.2349964705088137924875459464622098310997E-2Q,
-5.4431789996103111613753440311680967840214E-2Q,
-5.6546268881465384189752786409400404404794E-2Q,
-5.8693031345788023909329239565012647817664E-2Q,
-6.0871713627532018185577188079210189048340E-2Q,
-6.3081958078862169742820420185833800925568E-2Q,
-6.5323413029406789694910800219643791556918E-2Q,
-6.7595732653791419081537811574227049288168E-2Q
};

/* ln(2) = ln2a + ln2b with extended precision. */
static const __float128
ln2a = 6.93145751953125e-1Q,
ln2b = 1.4286068203094172321214581765680755001344E-6Q;

__float128
logq (__float128 x)
{
__float128 z, y, w;
ieee854_float128 u, t;
unsigned int m;
int k, e;

u.value = x;
m = u.words32.w0;

/* Extract exponent and reduce domain to 0.703125 <= u < 1.40625 */
e = (int) (m >> 16) - (int) 0x3ffe;
m &= 0xffff;
u.words32.w0 = m | 0x3ffe0000;
m |= 0x10000;
/* Find lookup table index k from high order bits of the significand. */
if (m < 0x16800)
{
k = (m - 0xff00) >> 9;
/* t is the argument 0.5 + (k+26)/128
of the nearest item to u in the lookup table. */
t.words32.w0 = 0x3fff0000 + (k << 9);
t.words32.w1 = 0;
t.words32.w2 = 0;
t.words32.w3 = 0;
u.words32.w0 += 0x10000;
e -= 1;
k += 64;
}
else
{
k = (m - 0xfe00) >> 10;
t.words32.w0 = 0x3ffe0000 + (k << 10);
t.words32.w1 = 0;
t.words32.w2 = 0;
t.words32.w3 = 0;
}
/* On this interval the table is not used due to cancellation error. */
if ((x <= 1.0078125Q) && (x >= 0.9921875Q))
{
z = x - 1.0Q;
k = 64;
t.value = 1.0Q;
e = 0;
}
else
{
/* log(u) = log( t u/t ) = log(t) + log(u/t)
log(t) is tabulated in the lookup table.
Express log(u/t) = log(1+z), where z = u/t - 1 = (u-t)/t.
cf. Cody & Waite. */
z = (u.value - t.value) / t.value;
}
/* Series expansion of log(1+z). */
w = z * z;
y = ((((((((((((l15 * z
+ l14) * z
+ l13) * z
+ l12) * z
+ l11) * z
+ l10) * z
+ l9) * z
+ l8) * z
+ l7) * z
+ l6) * z
+ l5) * z
+ l4) * z
+ l3) * z * w;
y -= 0.5 * w;
y += e * ln2b; /* Base 2 exponent offset times ln(2). */
y += z;
y += logtbl[k-26]; /* log(t) - (t-1) */
y += (t.value - 1.0Q);
y += e * ln2a;
return y;
}

static const __float128 bp[] = {
1.0Q,
1.5Q,
};

/* log_2(1.5) */
static const __float128 dp_h[] = {
0.0,
5.8496250072115607565592654282227158546448E-1Q
};

/* Low part of log_2(1.5) */
static const __float128 dp_l[] = {
0.0,
1.0579781240112554492329533686862998106046E-16Q
};

static const __float128
two = 2.0Q,
two113 = 1.0384593717069655257060992658440192E34Q,
tiny = 1.0e-3000Q;

/* 3/2 log x = 3 z + z^3 + z^3 (z^2 R(z^2))
z = (x-1)/(x+1)
1 <= x <= 1.25
Peak relative error 2.3e-37 */
static const __float128 LN[] =
{
-3.0779177200290054398792536829702930623200E1Q,
6.5135778082209159921251824580292116201640E1Q,
-4.6312921812152436921591152809994014413540E1Q,
1.2510208195629420304615674658258363295208E1Q,
-9.9266909031921425609179910128531667336670E-1Q
};
static const __float128 LD[] =
{
-5.129862866715009066465422805058933131960E1Q,
1.452015077564081884387441590064272782044E2Q,
-1.524043275549860505277434040464085593165E2Q,
7.236063513651544224319663428634139768808E1Q,
-1.494198912340228235853027849917095580053E1Q
/* 1.0E0 */
};

/* exp(x) = 1 + x - x / (1 - 2 / (x - x^2 R(x^2)))
0 <= x <= 0.5
Peak relative error 5.7e-38 */
static const __float128 PN[] =
{
5.081801691915377692446852383385968225675E8Q,
9.360895299872484512023336636427675327355E6Q,
4.213701282274196030811629773097579432957E4Q,
5.201006511142748908655720086041570288182E1Q,
9.088368420359444263703202925095675982530E-3Q,
};
static const __float128 PD[] =
{
3.049081015149226615468111430031590411682E9Q,
1.069833887183886839966085436512368982758E8Q,
8.259257717868875207333991924545445705394E5Q,
1.872583833284143212651746812884298360922E3Q,
/* 1.0E0 */
};

static const __float128
/* ln 2 */
lg2 = 6.9314718055994530941723212145817656807550E-1Q,
lg2_h = 6.9314718055994528622676398299518041312695E-1Q,
lg2_l = 2.3190468138462996154948554638754786504121E-17Q,
ovt = 8.0085662595372944372e-0017Q,
/* 2/(3*log(2)) */
cp = 9.6179669392597560490661645400126142495110E-1Q,
cp_h = 9.6179669392597555432899980587535537779331E-1Q,
cp_l = 5.0577616648125906047157785230014751039424E-17Q;

__float128
powq (__float128 x, __float128 y)
{
__float128 z, ax, z_h, z_l, p_h, p_l;
__float128 y1, t1, t2, r, s, t, u, v, w;
__float128 s2, s_h, s_l, t_h, t_l;
int i, j, k, n;
unsigned ix;
int hx;
ieee854_float128 o, p;

p.value = x;
hx = p.words32.w0;
ix = hx & 0x7fffffff;

ax = x;

n = 0;
/* take care subnormal number */
if (ix < 0x00010000)
{
ax *= two113;
n -= 113;
o.value = ax;
ix = o.words32.w0;
}
n += ((ix) >> 16) - 0x3fff;
j = ix & 0x0000ffff;
/* determine interval */
ix = j | 0x3fff0000; /* normalize ix */
if (j <= 0x3988)
k = 0; /* |x|<sqrt(3/2) */
else if (j < 0xbb67)
k = 1; /* |x|<sqrt(3) */
else
{
k = 0;
n += 1;
ix -= 0x00010000;
}

o.value = ax;
o.words32.w0 = ix;
ax = o.value;

/* compute s = s_h+s_l = (x-1)/(x+1) or (x-1.5)/(x+1.5) */
u = ax - bp[k]; /* bp[0]=1.0, bp[1]=1.5 */
v = one / (ax + bp[k]);
s = u * v;
s_h = s;

o.value = s_h;
o.words32.w3 = 0;
o.words32.w2 &= 0xf8000000;
s_h = o.value;
/* t_h=ax+bp[k] High */
t_h = ax + bp[k];
o.value = t_h;
o.words32.w3 = 0;
o.words32.w2 &= 0xf8000000;
t_h = o.value;
t_l = ax - (t_h - bp[k]);
s_l = v * ((u - s_h * t_h) - s_h * t_l);
/* compute log(ax) */
s2 = s * s;
u = LN[0] + s2 * (LN[1] + s2 * (LN[2] + s2 * (LN[3] + s2 * LN[4])));
v = LD[0] + s2 * (LD[1] + s2 * (LD[2] + s2 * (LD[3] + s2 * (LD[4] + s2))));
r = s2 * s2 * u / v;
r += s_l * (s_h + s);
s2 = s_h * s_h;
t_h = 3.0 + s2 + r;
o.value = t_h;
o.words32.w3 = 0;
o.words32.w2 &= 0xf8000000;
t_h = o.value;
t_l = r - ((t_h - 3.0) - s2);
/* u+v = s*(1+...) */
u = s_h * t_h;
v = s_l * t_h + t_l * s;
/* 2/(3log2)*(s+...) */
p_h = u + v;
o.value = p_h;
o.words32.w3 = 0;
o.words32.w2 &= 0xf8000000;
p_h = o.value;
p_l = v - (p_h - u);
z_h = cp_h * p_h; /* cp_h+cp_l = 2/(3*log2) */
z_l = cp_l * p_h + p_l * cp + dp_l[k];
/* log2(ax) = (s+..)*2/(3*log2) = n + dp_h + z_h + z_l */
t = (__float128) n;
t1 = (((z_h + z_l) + dp_h[k]) + t);
o.value = t1;
o.words32.w3 = 0;
o.words32.w2 &= 0xf8000000;
t1 = o.value;
t2 = z_l - (((t1 - t) - dp_h[k]) - z_h);
s = one;

/* split up y into y1+y2 and compute (y1+y2)*(t1+t2) */
y1 = y;
o.value = y1;
o.words32.w3 = 0;
o.words32.w2 &= 0xf8000000;
y1 = o.value;
p_l = (y - y1) * t1 + y * t2;
p_h = y1 * t1;
z = p_l + p_h;
o.value = z;
j = o.words32.w0;
/* compute 2**(p_h+p_l) */
i = j & 0x7fffffff;
k = (i >> 16) - 0x3fff;
n = 0;
if (i > 0x3ffe0000)
{ /* if |z| > 0.5, set n = [z+0.5] */
n = z + 0.5Q;
t = n;
p_h -= t;
}
t = p_l + p_h;
o.value = t;
o.words32.w3 = 0;
o.words32.w2 &= 0xf8000000;
t = o.value;
u = t * lg2_h;
v = (p_l - (t - p_h)) * lg2 + t * lg2_l;
z = u + v;
w = v - (z - u);
/* exp(z) */
t = z * z;
u = PN[0] + t * (PN[1] + t * (PN[2] + t * (PN[3] + t * PN[4])));
v = PD[0] + t * (PD[1] + t * (PD[2] + t * (PD[3] + t)));
t1 = z - t * u / v;
r = (z * t1) / (t1 - two) - (w + z * w);
z = one - (r - z);
o.value = z;
j = o.words32.w0;
j += (n << 16);
if ((j >> 16) <= 0)
z = scalbnq (z, n); /* subnormal output */
else
{
o.words32.w0 = j;
z = o.value;
}
return s * z;
}

static const __float128
two114 = 2.0769187434139310514121985316880384E+34Q, /* 0x4071000000000000, 0 */
twom114 = 4.8148248609680896326399448564623183E-35Q;/* 0x3F8D000000000000, 0 */

__float128
scalbnq (__float128 x, int n)
{
long long k,hx,lx;
GET_FLT128_WORDS64(hx,lx,x);
k = (hx>>48)&0x7fff; /* extract exponent */
if (k==0) { /* 0 or subnormal x */
if ((lx|(hx&0x7fffffffffffffffULL))==0) return x; /* +-0 */
x *= two114;
GET_FLT128_MSW64(hx,x);
k = ((hx>>48)&0x7fff) - 114;
}
if (k==0x7fff) return x+x; /* NaN or Inf */
/* Now k and n are bounded we know that k = k+n does not
overflow. */
k = k+n;
if (k > 0) /* normal result */
{SET_FLT128_MSW64(x,(hx&0x8000ffffffffffffULL)|(k<<48)); return x;}
if (k <= -114)
k += 114; /* subnormal result */
SET_FLT128_MSW64(x,(hx&0x8000ffffffffffffULL)|(k<<48));
return x*twom114;
}

const int tbl_cnt=3;
const double tbl[tbl_cnt]={1.0,1.0,2.0};

ifstream fin("fact.in");
ofstream fout("fact.out");

int main()
{
long long n;
int k;
fin>>n>>k;
if(n<tbl_cnt)
{
fout.precision(k);
fout<<tbl[n]<<"e+0\n";
return 0;
}
__float128 ans=lgammaq(n+1.0Q)/M_LN10q;
unsigned long long len=ans;
ans=powq(10.0Q,ans-len+k-1);
long long frac=ans;
ans-=frac;
if(ans>=0.5Q)
frac++;
stringstream ss;
ss<<frac;
string s=ss.str();
while(s[s.length()-1]=='0')
s.erase(s.length()-1);
if(s.length()>1)
s.insert(1,1,'.');
fout<<s<<"e+"<<len<<endl;
return 0;
}

lasers.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("lasers.in");
ofstream fout("lasers.out");
const int N = 300005, INF = 0x3f3f3f3f;
int x[N], y[N], d[N * 2];
pair<int, int> e[N];
vector<int> mat[N * 2];
int main()
{
int n, sx, sy, tx, ty;
fin >> n >> sx >> sy >> tx >> ty;
for (int i = 1; i <= n; i++)
{
fin >> e[i].first >> e[i].second;
x[i] = e[i].first;
y[i] = e[i].second;
}
x[n + 1] = sx;
x[n + 2] = tx;
y[n + 1] = sy;
y[n + 2] = ty;
sort(x + 1, x + n + 3);
sort(y + 1, y + n + 3);
sx = lower_bound(x + 1, x + n + 3, sx) - x;
sy = lower_bound(y + 1, y + n + 3, sy) - y + n + 2;
tx = lower_bound(x + 1, x + n + 3, tx) - x;
ty = lower_bound(y + 1, y + n + 3, ty) - y + n + 2;
for (int i = 1; i <= n; i++)
{
e[i].first = lower_bound(x + 1, x + n + 3, e[i].first) - x;
e[i].second = lower_bound(y + 1, y + n + 3, e[i].second) - y + n + 2;
mat[e[i].first].push_back(e[i].second);
mat[e[i].second].push_back(e[i].first);
}
fill(d + 1, d + n + 2 + n + 2 + 1, INF);
d[sx] = d[sy] = 0;
queue<int> Q;
Q.push(sx);
Q.push(sy);
while (!Q.empty())
{
int k = Q.front();
Q.pop();
for (auto v : mat[k])
if (d[v] == INF)
{
d[v] = d[k] + 1;
Q.push(v);
}
}
fout << min(d[tx], d[ty]) << endl;
return 0;
}

bales.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("bales.in");
ofstream fout("bales.out");
const int N = 1000005, M = 300005;
struct quest
{
int l, r, min, id;
bool operator<(const quest &rhs) const
{
return min > rhs.min;
}
} a[M], b[M];
int n, m, f[N];
int getf(int x)
{
return f[x] == x ? x : f[x] = getf(f[x]);
}
bool check(int mid)
{
int cc = 0;
for (int i = 1; i <= m; i++)
if (a[i].id <= mid)
b[++cc] = a[i];
for (int i = 0; i <= n; i++)
f[i] = i;
for (int i = 1, j; i <= cc; i = j)
{
int minx = b[i].l, maxx = b[i].l, miny = b[i].r, maxy = b[i].r;
for (j = i + 1; j <= cc && b[j].min == b[i].min; j++)
{
minx = min(minx, b[j].l);
maxx = max(maxx, b[j].l);
miny = min(miny, b[j].r);
maxy = max(maxy, b[j].r);
}
if (maxx > getf(miny))
return false;
while (minx <= maxy)
if (getf(maxy) == maxy)
f[maxy--] = getf(minx - 1);
else
maxy = getf(maxy);
}
return true;
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> a[i].l >> a[i].r >> a[i].min;
a[i].id = i;
}
sort(a + 1, a + m + 1);
int l = 1, r = m, ans = 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
fout << (ans + 1) % (m + 1) << endl;
return 0;
}

day2

corral.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <fstream>
#include <algorithm>
#include <utility>
#include <limits>
using namespace std;
ifstream fin("corral.in");
ofstream fout("corral.out");
const int N = 3005;
const long long INF = numeric_limits<long long>::max();
pair<long long, long long> p[N];
long long x[N], y[N];
short s[N][N];
int main()
{
int c, n;
fin >> c >> n;
for (int i = 1; i <= n; i++)
{
fin >> p[i].first >> p[i].second;
x[i] = p[i].first;
y[i] = p[i].second;
}
sort(x + 1, x + n + 1);
sort(y + 1, y + n + 1);
int xn = unique(x + 1, x + n + 1) - x - 1, yn = unique(y + 1, y + n + 1) - y - 1;
for (int i = 1; i <= n; i++)
{
p[i].first = lower_bound(x + 1, x + xn + 1, p[i].first) - x;
p[i].second = lower_bound(y + 1, y + yn + 1, p[i].second) - y;
s[p[i].first][p[i].second]++;
}
for (int i = 1; i <= xn; i++)
for (int j = 1; j <= yn; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
long long ans = INF;
x[xn + 1] = y[yn + 1] = INF;
for (int x1 = 1; x1 <= xn; x1++)
{
long long now = 0;
int x2 = x1 + 1, y1 = 1, y2 = 2, cnt = s[x2 - 1][y2 - 1] - s[x1 - 1][y2 - 1] - s[x2 - 1][y1 - 1] + s[x1 - 1][y1 - 1];
for (;;)
{
while (cnt < c && (x2 <= xn || y2 <= yn))
{
now = min(x[x2] - x[x1], y[y2] - y[y1]);
for (; x[x2] - x[x1] <= now; x2++)
;
for (; y[y2] - y[y1] <= now; y2++)
;
cnt = s[x2 - 1][y2 - 1] - s[x1 - 1][y2 - 1] - s[x2 - 1][y1 - 1] + s[x1 - 1][y1 - 1];
}
if (cnt < c)
break;
ans = min(ans, now + 1);
if (++y1 > yn)
break;
if (y2 == y1)
{
y2 = y1 + 1;
now = 0;
}
else
now -= y[y1] - y[y1 - 1];
for (; x[x2 - 1] - x[x1] > now; x2--)
;
cnt = s[x2 - 1][y2 - 1] - s[x1 - 1][y2 - 1] - s[x2 - 1][y1 - 1] + s[x1 - 1][y1 - 1];
}
}
fout << ans << endl;
return 0;
}

qkiller.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <fstream>
#include <ctime>
#include <algorithm>
using namespace std;
ifstream fin("qkiller.in");
ofstream fout("qkiller.out");
const int n = 100000, A = 48271, MOD = 2147483647;
int a[n + 5], id[n + 5], ans[n + 5];
int main()
{
int type;
fin >> type;
long long seed;
if (type == 4)
{
tm rec;
char c;
fin >> rec.tm_year >> c >> rec.tm_mon >> c >> rec.tm_mday >> rec.tm_hour >> c >> rec.tm_min >> c >> rec.tm_sec;
rec.tm_year -= 1900;
rec.tm_mon--;
seed = mktime(&rec);
}
for (int i = 1; i <= n; i++)
{
fin >> a[i];
id[i] = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
{
int pos;
switch (type)
{
case 1:
pos = (i + n) / 2;
break;
case 2:
pos = i;
break;
case 3:
pos = n;
break;
case 4:
seed = seed * A % MOD;
pos = seed % (n - i + 1) + i;
break;
}
ans[id[pos]] = a[i];
swap(id[i], id[pos]);
}
for (int i = 1; i <= n; i++)
fout << ans[i] << endl;
return 0;
}

landscape.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("landscape.in");
ofstream fout("landscape.out");
const int N = 100005;
int a[N], b[N];
int main()
{
int n, x, y, z;
fin >> n >> x >> y >> z;
for (int i = 1; i <= n; i++)
fin >> a[i] >> b[i];
priority_queue<int, vector<int>, greater<int>> q1, q2;
long long ans = 0;
for (int i = 1; i <= n; i++)
{
for (; a[i] > b[i]; a[i]--)
{
int now = y;
if (!q1.empty() && q1.top() + i * z < now)
{
now = q1.top() + i * z;
q1.pop();
}
ans += now;
q2.push(-now - i * z);
}
for (; a[i] < b[i]; a[i]++)
{
int now = x;
if (!q2.empty() && q2.top() + i * z < now)
{
now = q2.top() + i * z;
q2.pop();
}
ans += now;
q1.push(-now - i * z);
}
}
fout << ans << endl;
return 0;
}

removed

pair.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<fstream>
#include<algorithm>
#include<set>
using namespace std;
ifstream fin("pair.in");
ofstream fout("pair.out");
const int N=200005;
const long long INF=0x3f3f3f3f3f3f3f3fll;
pair<int,int> p[N];
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
fin>>p[i].first>>p[i].second;
sort(p+1,p+n+1);
long long ans=INF;
multiset<pair<int,int>> S;
int j=1;
for(int i=1;i<=n;i++)
{
for(;j<i&&(long long)(p[i].first-p[j].first)*(p[i].first-p[j].first)>=ans;j++)
S.erase(S.find(make_pair(p[j].second,p[j].first)));
auto ret=S.insert(make_pair(p[i].second,p[i].first));
for(auto it=ret;it--!=S.begin();)
{
int dy=p[i].second-it->first;
if((long long)dy*dy>=ans)
break;
int dx=p[i].first-it->second;
ans=min(ans,(long long)dx*dx+(long long)dy*dy);
}
for(auto it=ret;++it!=S.end();)
{
int dy=it->first-p[i].second;
if((long long)dy*dy>=ans)
break;
int dx=p[i].first-it->second;
ans=min(ans,(long long)dx*dx+(long long)dy*dy);
}
}
fout<<ans<<endl;
return 0;
}