CSES - Aalto Competitive Programming 2024 - wk1 - Mon - Results
Submission details
Task:Traffic jam
Sender:hungdojan
Submission time:2024-09-02 17:06:45 +0300
Language:Python3 (CPython3)
Status:READY
Result:
Test results
testverdicttime
#10.02 sdetails
#20.02 sdetails
#30.02 sdetails
#40.02 sdetails
#50.02 sdetails
#60.02 sdetails
#70.02 sdetails
#80.02 sdetails
#90.02 sdetails
#100.02 sdetails
#110.02 sdetails
#120.02 sdetails
#130.02 sdetails
#140.02 sdetails
#150.02 sdetails
#160.02 sdetails
#170.02 sdetails
#180.02 sdetails
#190.02 sdetails
#200.02 sdetails
#210.02 sdetails
#220.02 sdetails
#230.02 sdetails
#240.02 sdetails
#250.02 sdetails
#260.02 sdetails
#270.02 sdetails
#280.02 sdetails
#290.02 sdetails
#300.02 sdetails
#310.04 sdetails
#320.04 sdetails
#330.04 sdetails
#340.04 sdetails
#350.04 sdetails
#360.04 sdetails
#370.04 sdetails
#380.04 sdetails
#390.04 sdetails
#400.04 sdetails
#410.47 sdetails
#420.47 sdetails
#430.47 sdetails
#440.47 sdetails
#450.47 sdetails
#460.53 sdetails
#470.48 sdetails
#480.47 sdetails
#490.46 sdetails
#500.48 sdetails
#51--details
#52--details
#53--details
#54--details
#55--details
#56--details
#57--details
#58--details
#59--details
#60--details
#61--details
#62--details
#63--details
#64--details
#65--details
#66--details
#67--details
#68--details
#69--details
#70--details

Code

ran = {}

lof_ranges = []

def get_nearest_small(num, lof_ranges):
    for i, v in enumerate(lof_ranges):
        if v > num:
            return ran[lof_ranges[i-1]]
    else:
        return 0

def get_nearest_big(num, lof_ranges):
    for i, v in enumerate(lof_ranges):
        if v > num:
            print(num, v)
            return ran[lof_ranges[i-1]]
    else:
        return 0

def get_mids(fr, to, lof_ranges):
    return [i for i in lof_ranges if i >= fr and i <= to]

s = int(input())
for i in range(s):
    lof_ranges.sort()
    data = input().strip().split()
    fr, to = int(data[0]), int(data[1])

    lof_ranges.sort()
    # get start
    if fr not in ran:
        ran[fr] = get_nearest_small(fr, lof_ranges)

    # get end
    if to not in ran:
        ran[to] = get_nearest_big(to, lof_ranges)

    if fr not in lof_ranges:
        lof_ranges.append(fr)

    # get end
    if to not in lof_ranges:
        lof_ranges.append(to)

    lof_ranges.sort()
    # fill mid
    for i in get_mids(fr, to, lof_ranges):
        ran[i] += 1

    print(ran)

print(max(list(ran.values())))

Test details

Test 1

Verdict:

input
5
11 18
11 12
15 17
9 17
...

correct output
3

user output
{11: 1, 18: 1}
12 18
{11: 2, 18: 1, 12: 2}
17 18
{11: 2, 18: 1, 12: 2, 15: 3, 1...
Truncated

Test 2

Verdict:

input
5
3 9
7 20
15 20
3 19
...

correct output
3

user output
{3: 1, 9: 1}
{3: 1, 9: 2, 7: 2, 20: 1}
{3: 1, 9: 2, 7: 2, 20: 2, 15: ...
Truncated

Test 3

Verdict:

input
5
9 19
4 9
1 10
9 19
...

correct output
5

user output
{9: 1, 19: 1}
{9: 2, 19: 1, 4: 2}
10 19
{9: 3, 19: 1, 4: 3, 1: 2, 10: ...
Truncated

Test 4

Verdict:

input
5
3 12
2 11
12 15
17 18
...

correct output
3

user output
{3: 1, 12: 1}
11 12
{3: 2, 12: 1, 2: 2, 11: 2}
{3: 2, 12: 2, 2: 2, 11: 2, 15:...
Truncated

Test 5

Verdict:

input
5
18 20
15 19
11 13
4 14
...

correct output
3

user output
{18: 1, 20: 1}
19 20
{18: 2, 20: 1, 15: 2, 19: 2}
13 15
{18: 2, 20: 1, 15: 2, 19: 2, 1...
Truncated

Test 6

Verdict:

input
5
5 8
2 19
18 20
10 17
...

correct output
3

user output
{5: 1, 8: 1}
{5: 2, 8: 2, 2: 2, 19: 1}
{5: 2, 8: 2, 2: 2, 19: 2, 18: ...
Truncated

Test 7

Verdict:

input
5
2 18
1 19
7 8
3 5
...

correct output
3

user output
{2: 1, 18: 1}
{2: 2, 18: 2, 1: 2, 19: 1}
8 18
{2: 2, 18: 2, 1: 2, 19: 1, 7: ...
Truncated

Test 8

Verdict:

input
5
2 20
5 15
10 16
7 20
...

correct output
4

user output
{2: 1, 20: 1}
15 20
{2: 1, 20: 1, 5: 2, 15: 2}
16 20
{2: 1, 20: 1, 5: 2, 15: 3, 10:...
Truncated

Test 9

Verdict:

input
5
8 18
1 11
17 20
5 5
...

correct output
3

user output
{8: 1, 18: 1}
11 18
{8: 2, 18: 1, 1: 2, 11: 2}
{8: 2, 18: 2, 1: 2, 11: 2, 17:...
Truncated

Test 10

Verdict:

input
5
1 1
3 8
7 11
3 10
...

correct output
4

user output
{1: 1}
{1: 1, 3: 1, 8: 1}
{1: 1, 3: 1, 8: 2, 7: 2, 11: 1...
Truncated

Test 11

Verdict:

input
10
11 13
8 12
9 15
6 17
...

correct output
8

user output
{11: 1, 13: 1}
12 13
{11: 2, 13: 1, 8: 2, 12: 2}
{11: 3, 13: 2, 8: 2, 12: 3, 9:...
Truncated

Test 12

Verdict:

input
10
2 9
8 20
4 15
8 19
...

correct output
8

user output
{2: 1, 9: 1}
{2: 1, 9: 2, 8: 2, 20: 1}
15 20
{2: 1, 9: 3, 8: 3, 20: 1, 4: 2...
Truncated

Test 13

Verdict:

input
10
7 9
4 4
1 5
14 19
...

correct output
5

user output
{7: 1, 9: 1}
{7: 1, 9: 1, 4: 2}
5 7
{7: 1, 9: 1, 4: 3, 1: 2, 5: 3}
{7: 1, 9: 1, 4: 3, 1: 2
...
Truncated

Test 14

Verdict:

input
10
12 18
1 2
3 15
1 17
...

correct output
6

user output
{12: 1, 18: 1}
2 12
{12: 1, 18: 1, 1: 2, 2: 2}
15 18
{12: 2, 18: 1, 1: 2, 2: 2, 3: ...
Truncated

Test 15

Verdict:

input
10
5 20
3 19
11 20
4 5
...

correct output
8

user output
{5: 1, 20: 1}
19 20
{5: 2, 20: 1, 3: 2, 19: 2}
{5: 2, 20: 2, 3: 2, 19: 3, 11:...
Truncated

Test 16

Verdict:

input
10
5 13
2 8
16 18
8 17
...

correct output
8

user output
{5: 1, 13: 1}
8 13
{5: 2, 13: 1, 2: 2, 8: 2}
{5: 2, 13: 1, 2: 2, 8: 2, 16: ...
Truncated

Test 17

Verdict:

input
10
12 18
2 19
7 11
5 13
...

correct output
7

user output
{12: 1, 18: 1}
{12: 2, 18: 2, 2: 2, 19: 1}
11 12
{12: 2, 18: 2, 2: 2, 19: 1, 7:...
Truncated

Test 18

Verdict:

input
10
2 11
5 6
11 16
2 7
...

correct output
6

user output
{2: 1, 11: 1}
6 11
{2: 1, 11: 1, 5: 2, 6: 2}
{2: 1, 11: 2, 5: 2, 6: 2, 16: ...
Truncated

Test 19

Verdict:

input
10
1 18
1 13
9 20
5 16
...

correct output
8

user output
{1: 1, 18: 1}
13 18
{1: 2, 18: 1, 13: 2}
{1: 2, 18: 2, 13: 3, 9: 3, 20:...
Truncated

Test 20

Verdict:

input
10
1 5
8 18
9 11
3 10
...

correct output
6

user output
{1: 1, 5: 1}
{1: 1, 5: 1, 8: 1, 18: 1}
11 18
{1: 1, 5: 1, 8: 1, 18: 1, 9: 2...
Truncated

Test 21

Verdict:

input
100
331945 344878
23242 358577
265284 432575
383635 510646
...

correct output
58

user output
{331945: 1, 344878: 1}
{331945: 2, 344878: 2, 23242: ...
Truncated

Test 22

Verdict:

input
100
11714 252232
50579 603138
410587 435681
554555 564048
...

correct output
57

user output
{11714: 1, 252232: 1}
{11714: 1, 252232: 2, 50579: 2...
Truncated

Test 23

Verdict:

input
100
263708 329159
111946 492424
15682 49655
563433 573443
...

correct output
50

user output
{263708: 1, 329159: 1}
{263708: 2, 329159: 2, 111946:...
Truncated

Test 24

Verdict:

input
100
124241 333145
42778 460029
121802 428316
38571 508035
...

correct output
65

user output
{124241: 1, 333145: 1}
{124241: 2, 333145: 2, 42778: ...
Truncated

Test 25

Verdict:

input
100
541635 584899
544732 562143
219469 330988
104454 142828
...

correct output
56

user output
{541635: 1, 584899: 1}
562143 584899
{541635: 1, 584899: 1, 544732:...
Truncated

Test 26

Verdict:

input
100
134271 466244
33376 118232
293306 526654
73518 502821
...

correct output
56

user output
{134271: 1, 466244: 1}
118232 134271
{134271: 1, 466244: 1, 33376: ...
Truncated

Test 27

Verdict:

input
100
462552 540038
297097 573072
171690 200795
126658 322135
...

correct output
56

user output
{462552: 1, 540038: 1}
{462552: 2, 540038: 2, 297097:...
Truncated

Test 28

Verdict:

input
100
46155 255469
137504 304813
257937 471726
192928 376970
...

correct output
53

user output
{46155: 1, 255469: 1}
{46155: 1, 255469: 2, 137504: ...
Truncated

Test 29

Verdict:

input
100
113815 528285
6723 287126
379269 585812
144823 151502
...

correct output
50

user output
{113815: 1, 528285: 1}
287126 528285
{113815: 2, 528285: 1, 6723: 2...
Truncated

Test 30

Verdict:

input
100
6275 391402
25919 220441
303554 385921
102892 301894
...

correct output
54

user output
{6275: 1, 391402: 1}
220441 391402
{6275: 1, 391402: 1, 25919: 2,...
Truncated

Test 31

Verdict:

input
200
349680 466526
56164 180703
12552 516494
299148 516954
...

correct output
108

user output
{349680: 1, 466526: 1}
180703 349680
{349680: 1, 466526: 1, 56164: ...
Truncated

Test 32

Verdict:

input
200
109035 192453
41315 154620
11780 131858
402050 438594
...

correct output
112

user output
{109035: 1, 192453: 1}
154620 192453
{109035: 2, 192453: 1, 41315: ...
Truncated

Test 33

Verdict:

input
200
93244 232995
269893 529384
360329 447612
317907 528260
...

correct output
97

user output
{93244: 1, 232995: 1}
{93244: 1, 232995: 1, 269893: ...
Truncated

Test 34

Verdict:

input
200
421407 470386
352706 367345
143675 582521
502292 519820
...

correct output
114

user output
{421407: 1, 470386: 1}
367345 421407
{421407: 1, 470386: 1, 352706:...
Truncated

Test 35

Verdict:

input
200
143318 310854
401813 557598
237535 467641
34287 398641
...

correct output
96

user output
{143318: 1, 310854: 1}
{143318: 1, 310854: 1, 401813:...
Truncated

Test 36

Verdict:

input
200
9076 513399
469260 492086
108204 544191
357676 381009
...

correct output
108

user output
{9076: 1, 513399: 1}
492086 513399
{9076: 1, 513399: 1, 469260: 2...
Truncated

Test 37

Verdict:

input
200
135056 264320
197575 327883
316431 564474
33682 362951
...

correct output
103

user output
{135056: 1, 264320: 1}
{135056: 1, 264320: 2, 197575:...
Truncated

Test 38

Verdict:

input
200
178226 450594
82713 109947
249837 320920
281091 510627
...

correct output
107

user output
{178226: 1, 450594: 1}
109947 178226
{178226: 1, 450594: 1, 82713: ...
Truncated

Test 39

Verdict:

input
200
393373 398425
45975 568291
305719 324476
261670 442591
...

correct output
108

user output
{393373: 1, 398425: 1}
{393373: 2, 398425: 2, 45975: ...
Truncated

Test 40

Verdict:

input
200
58993 496474
260365 371793
460435 493947
56859 249644
...

correct output
105

user output
{58993: 1, 496474: 1}
371793 496474
{58993: 1, 496474: 1, 260365: ...
Truncated

Test 41

Verdict:

input
1000
58068 355725
395347 536742
358259 542973
346571 577267
...

correct output
516

user output
{58068: 1, 355725: 1}
{58068: 1, 355725: 1, 395347: ...
Truncated

Test 42

Verdict:

input
1000
29471 589969
57506 483432
174866 389980
250305 411196
...

correct output
496

user output
{29471: 1, 589969: 1}
483432 589969
{29471: 1, 589969: 1, 57506: 2...
Truncated

Test 43

Verdict:

input
1000
126086 545768
218902 424576
291340 394396
158589 441840
...

correct output
496

user output
{126086: 1, 545768: 1}
424576 545768
{126086: 1, 545768: 1, 218902:...
Truncated

Test 44

Verdict:

input
1000
312883 531822
243696 404697
422989 572761
111889 147621
...

correct output
516

user output
{312883: 1, 531822: 1}
404697 531822
{312883: 2, 531822: 1, 243696:...
Truncated

Test 45

Verdict:

input
1000
413156 580657
178086 312928
423093 540156
31969 390612
...

correct output
515

user output
{413156: 1, 580657: 1}
312928 413156
{413156: 1, 580657: 1, 178086:...
Truncated

Test 46

Verdict:

input
1000
20157 526286
133047 421009
168036 352185
262047 570796
...

correct output
484

user output
{20157: 1, 526286: 1}
421009 526286
{20157: 1, 526286: 1, 133047: ...
Truncated

Test 47

Verdict:

input
1000
186252 329188
204116 431319
314149 576299
178378 570064
...

correct output
526

user output
{186252: 1, 329188: 1}
{186252: 1, 329188: 2, 204116:...
Truncated

Test 48

Verdict:

input
1000
257494 501892
189236 290808
417823 492693
503108 553381
...

correct output
529

user output
{257494: 1, 501892: 1}
290808 501892
{257494: 2, 501892: 1, 189236:...
Truncated

Test 49

Verdict:

input
1000
440937 546476
103321 263496
339461 417536
34170 174218
...

correct output
487

user output
{440937: 1, 546476: 1}
263496 440937
{440937: 1, 546476: 1, 103321:...
Truncated

Test 50

Verdict:

input
1000
181034 522437
484192 595527
172323 543908
209577 405953
...

correct output
528

user output
{181034: 1, 522437: 1}
{181034: 1, 522437: 2, 484192:...
Truncated

Test 51

Verdict:

input
10000
45796 389604
54588 554625
6480 230292
132011 412509
...

correct output
5040

user output
(empty)

Test 52

Verdict:

input
10000
173017 222949
17536 418698
371928 579501
194960 329203
...

correct output
4932

user output
(empty)

Test 53

Verdict:

input
10000
35688 519491
36083 511716
144944 225431
254661 329431
...

correct output
5084

user output
(empty)

Test 54

Verdict:

input
10000
150309 588246
41663 417148
272164 454943
378370 404808
...

correct output
5005

user output
(empty)

Test 55

Verdict:

input
10000
23324 368919
118406 505285
302915 471836
256075 427134
...

correct output
5028

user output
(empty)

Test 56

Verdict:

input
10000
14733 277050
272054 385434
186503 304365
65427 409189
...

correct output
5071

user output
(empty)

Test 57

Verdict:

input
10000
426026 440631
53008 185605
323120 363881
433574 569197
...

correct output
5028

user output
(empty)

Test 58

Verdict:

input
10000
215735 571270
84210 264983
139013 280706
62911 316988
...

correct output
5036

user output
(empty)

Test 59

Verdict:

input
10000
100867 232727
291085 542548
180752 519986
70248 552319
...

correct output
5018

user output
(empty)

Test 60

Verdict:

input
10000
77563 330781
3428 282943
62433 482602
120814 489906
...

correct output
4974

user output
(empty)

Test 61

Verdict:

input
100000
246586 530849
324115 389522
33488 599309
67846 517025
...

correct output
50092

user output
(empty)

Test 62

Verdict:

input
100000
151769 163196
411638 428029
27881 555301
161709 194138
...

correct output
49927

user output
(empty)

Test 63

Verdict:

input
100000
39491 226537
118226 481781
97491 575030
110949 445551
...

correct output
50015

user output
(empty)

Test 64

Verdict:

input
100000
69590 283153
300522 495108
223274 368388
62247 218684
...

correct output
49913

user output
(empty)

Test 65

Verdict:

input
100000
504946 530310
224245 261619
63385 352368
19219 407804
...

correct output
49833

user output
(empty)

Test 66

Verdict:

input
100000
566124 598194
184196 411065
332387 465916
254612 406138
...

correct output
49947

user output
(empty)

Test 67

Verdict:

input
100000
449821 474093
156077 417344
383973 444464
55148 413842
...

correct output
50077

user output
(empty)

Test 68

Verdict:

input
100000
68643 447506
360603 515177
141640 589407
316333 550205
...

correct output
50142

user output
(empty)

Test 69

Verdict:

input
100000
10579 453250
257955 382091
511698 539259
14502 161173
...

correct output
50313

user output
(empty)

Test 70

Verdict:

input
100000
182036 358379
286536 600845
149433 208473
431529 460545
...

correct output
49932

user output
(empty)