CSES - Datatähti 2024 loppu - Results
Submission details
Task:Retkeily
Sender:EeliH
Submission time:2024-01-20 15:49:39 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.08 s1, 2, 3, 4details
#2ACCEPTED0.08 s1, 2, 3, 4details
#3ACCEPTED0.08 s1, 2, 3, 4details
#4ACCEPTED0.08 s1, 2, 3, 4details
#5ACCEPTED0.08 s1, 2, 3, 4details
#60.07 s1, 2, 4details
#70.07 s1, 2, 4details
#8ACCEPTED0.08 s1, 2, 3, 4details
#90.07 s1, 2, 4details
#10ACCEPTED0.11 s1, 2, 3, 4details
#110.07 s1, 2, 4details
#120.07 s1, 2, 4details
#130.07 s1, 2, 4details
#140.07 s1, 2, 4details
#150.07 s1, 2, 4details
#160.08 s2, 4details
#170.08 s2, 4details
#180.09 s2, 4details
#19ACCEPTED0.56 s2, 3, 4details
#200.13 s2, 4details
#21--2, 3, 4details
#22ACCEPTED0.08 s1, 3, 4details
#23ACCEPTED0.15 s1, 3, 4details
#24ACCEPTED0.82 s3, 4details
#25--3, 4details
#26--3, 4details
#27--3, 4details
#28--3, 4details
#290.07 s1, 4details
#300.07 s1, 4details
#310.07 s1, 4details
#320.07 s1, 4details
#330.07 s1, 4details
#340.07 s1, 4details
#350.07 s1, 4details
#360.07 s1, 4details
#370.09 s4details
#380.24 s4details
#390.24 s4details
#400.24 s4details
#410.23 s4details

Code

#include <bits/stdc++.h>
using namespace std;

#define MAGIC 22

int n, m;
vector<pair<int, int>> varatutxy;
vector<pair<int, int>> vapaatxy;
vector<pair<int, int>> varatutyx;
vector<pair<int, int>> vapaatyx;
set<int> takencols[1000039];
set<int> takenrows[1000093];

bool is_dist_free(int x, int y, int n)
{
    cerr << x << " " << y << " " << n << endl;
    assert(n <= 10);
    
    for (int i = 0; i < n + 1; i++) {
        if (takencols[x - n + i + MAGIC].contains(y + i)) {
            return false;
        }
    }

    for (int i = 0; i < n + 1; i++) {
        if (takencols[x + i + MAGIC].contains(y + n - i)) {
            return false;
        }
    }

    for (int i = 0; i < n + 1; i++) {
        if (takencols[x + n - i + MAGIC].contains(y - i)) {
            return false;
        }
    }

    for (int i = 0; i < n + 1; i++) {
        if (takencols[x - i + MAGIC].contains(y - n + i)) {
            return false;
        }
    }

    return true;
}

int main()
{
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        varatutxy.push_back(make_pair(x, y));
        varatutyx.push_back(make_pair(y, x));
        takencols[x + MAGIC].insert(y);
        takenrows[y + MAGIC].insert(x);
    }

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        vapaatxy.push_back(make_pair(x, y));
        vapaatyx.push_back(make_pair(y, x));
    }

    int maxd = 0;
    for (int i = 0; i < m; i++) {
        cerr << "checking " << vapaatxy[i].first << ", " << vapaatxy[i].second << endl;
        for (int j = 1;; j++) {
            if (!is_dist_free(vapaatxy[i].first, vapaatxy[i].second, j)) {
                cerr << "found " << j << endl;
                maxd = max(maxd, j);
                break;
            }
        }
    }

    cout << maxd << endl;
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1 1
6 6
8 9

correct output
5

user output
5

Error:
checking 8, 9
8 9 1
8 9 2
8 9 3
8 9 4
8 9 5
found 5

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
5 5
5 10
8 10
1 2
4 10
...

correct output
4

user output
4

Error:
checking 1, 4
1 4 1
1 4 2
found 2
checking 2, 4
2 4 1
found 1
checking 4, 7
4 7 1
4 7 2
4...

Test 3

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
10 10
5 2
1 10
6 10
5 5
...

correct output
5

user output
5

Error:
checking 6, 7
6 7 1
6 7 2
6 7 3
found 3
checking 2, 5
2 5 1
found 1
checking 6, 6
6 6 1
6...

Test 4

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
10 5
6 1
8 9
3 2
6 6
...

correct output
3

user output
3

Error:
checking 1, 2
1 2 1
found 1
checking 5, 5
5 5 1
5 5 2
found 2
checking 7, 3
7 3 1
7 3 2
7...

Test 5

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
5 10
10 10
6 2
10 9
8 7
...

correct output
7

user output
7

Error:
checking 3, 2
3 2 1
3 2 2
3 2 3
found 3
checking 10, 3
10 3 1
10 3 2
10 3 3
10 3 4
10 3 5...

Test 6

Group: 1, 2, 4

Verdict:

input
1 1
55 68
28 42

correct output
53

user output
(empty)

Error:
checking 28, 42
28 42 1
28 42 2
28 42 3
28 42 4
28 42 5
28 42 6
28 42 7
28 42 8
28 42 9
28...

Test 7

Group: 1, 2, 4

Verdict:

input
100 100
52 56
58 96
3 99
18 1
...

correct output
20

user output
(empty)

Error:
checking 70, 26
70 26 1
70 26 2
70 26 3
70 26 4
70 26 5
found 5
checking 35, 33
35 33 1
35...

Test 8

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1000 100
60 40
68 47
30 32
74 52
...

correct output
5

user output
5

Error:
checking 51, 96
51 96 1
51 96 2
51 96 3
found 3
checking 63, 15
63 15 1
63 15 2
found 2
ch...

Test 9

Group: 1, 2, 4

Verdict:

input
100 1000
44 26
18 81
18 6
83 90
...

correct output
20

user output
(empty)

Error:
checking 84, 13
84 13 1
84 13 2
84 13 3
84 13 4
84 13 5
found 5
checking 49, 75
49 75 1
49...

Test 10

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
1000 1000
15 13
23 79
81 43
30 40
...

correct output
7

user output
7

Error:
checking 14, 5
14 5 1
found 1
checking 18, 60
18 60 1
18 60 2
18 60 3
18 60 4
18 60 5
18 6...

Test 11

Group: 1, 2, 4

Verdict:

input
1 1
948 495
227 149

correct output
1067

user output
(empty)

Error:
checking 227, 149
227 149 1
227 149 2
227 149 3
227 149 4
227 149 5
227 149 6
227 149 7
22...

Test 12

Group: 1, 2, 4

Verdict:

input
100 100
114 530
748 841
612 709
810 232
...

correct output
203

user output
(empty)

Error:
checking 204, 720
204 720 1
204 720 2
204 720 3
204 720 4
204 720 5
204 720 6
204 720 7
20...

Test 13

Group: 1, 2, 4

Verdict:

input
1000 100
225 82
265 691
978 367
993 396
...

correct output
50

user output
(empty)

Error:
checking 951, 450
951 450 1
951 450 2
951 450 3
951 450 4
951 450 5
951 450 6
951 450 7
95...

Test 14

Group: 1, 2, 4

Verdict:

input
100 1000
848 668
189 716
451 80
626 973
...

correct output
192

user output
(empty)

Error:
checking 263, 214
263 214 1
263 214 2
263 214 3
263 214 4
263 214 5
263 214 6
263 214 7
26...

Test 15

Group: 1, 2, 4

Verdict:

input
1000 1000
931 656
382 809
666 609
1000 923
...

correct output
66

user output
(empty)

Error:
checking 914, 970
914 970 1
914 970 2
914 970 3
914 970 4
914 970 5
914 970 6
914 970 7
91...

Test 16

Group: 2, 4

Verdict:

input
10000 1000
961 158
561 313
991 125
821 964
...

correct output
18

user output
(empty)

Error:
checking 880, 965
880 965 1
880 965 2
880 965 3
880 965 4
880 965 5
found 5
checking 493,...

Test 17

Group: 2, 4

Verdict:

input
1000 10000
428 1000
485 958
46 915
582 127
...

correct output
67

user output
(empty)

Error:
checking 246, 243
246 243 1
246 243 2
246 243 3
246 243 4
246 243 5
246 243 6
246 243 7
24...

Test 18

Group: 2, 4

Verdict:

input
10000 10000
503 849
367 829
448 926
362 512
...

correct output
22

user output
(empty)

Error:
checking 763, 787
763 787 1
found 1
checking 410, 716
410 716 1
410 716 2
410 716 3
410 71...

Test 19

Group: 2, 3, 4

Verdict: ACCEPTED

input
100000 10000
111 705
808 24
69 858
961 122
...

correct output
7

user output
7

Error:
checking 174, 739
174 739 1
174 739 2
found 2
checking 720, 340
720 340 1
720 340 2
720 34...

Test 20

Group: 2, 4

Verdict:

input
10000 100000
844 874
339 315
819 918
627 936
...

correct output
27

user output
(empty)

Error:
checking 428, 90
428 90 1
428 90 2
428 90 3
428 90 4
found 4
checking 12, 284
12 284 1
12...

Test 21

Group: 2, 3, 4

Verdict:

input
100000 100000
100 468
303 899
784 458
505 54
...

correct output
8

user output
(empty)

Test 22

Group: 1, 3, 4

Verdict: ACCEPTED

input
10 10
451219 220496
369161 161920
241139 700531
811276 993633
...

correct output
10

user output
10

Error:
checking 451225, 220495
451225 220495 1
451225 220495 2
451225 220495 3
451225 220495 4
45...

Test 23

Group: 1, 3, 4

Verdict: ACCEPTED

input
1000 1000
337358 113599
674585 852084
717817 983395
895431 391144
...

correct output
10

user output
10

Error:
checking 337356, 113605
337356 113605 1
337356 113605 2
337356 113605 3
337356 113605 4
33...

Test 24

Group: 3, 4

Verdict: ACCEPTED

input
10000 10000
636432 664736
341727 37864
469264 360610
545785 879043
...

correct output
10

user output
10

Error:
checking 636425, 664735
636425 664735 1
636425 664735 2
636425 664735 3
636425 664735 4
63...

Test 25

Group: 3, 4

Verdict:

input
100000 100000
750315 55215
550921 465416
435380 742666
288479 495099
...

correct output
7

user output
(empty)

Test 26

Group: 3, 4

Verdict:

input
100000 100000
416825 677767
347155 162523
602643 936386
181956 517732
...

correct output
8

user output
(empty)

Test 27

Group: 3, 4

Verdict:

input
100000 100000
155202 457283
421100 55104
604625 136495
841749 569346
...

correct output
9

user output
(empty)

Test 28

Group: 3, 4

Verdict:

input
100000 100000
290146 808578
489810 268578
956361 635214
939844 534435
...

correct output
10

user output
(empty)

Test 29

Group: 1, 4

Verdict:

input
10 10
668880 791821
226050 188133
859493 736633
290460 838926
...

correct output
342068

user output
(empty)

Error:
checking 509805, 246446
509805 246446 1
509805 246446 2
509805 246446 3
509805 246446 4
50...

Test 30

Group: 1, 4

Verdict:

input
100 100
729367 697755
338457 742774
535371 701216
93743 555995
...

correct output
285526

user output
(empty)

Error:
checking 435238, 719559
435238 719559 1
435238 719559 2
435238 719559 3
435238 719559 4
43...

Test 31

Group: 1, 4

Verdict:

input
100 1000
50870 539657
476809 462765
311713 355546
901838 829393
...

correct output
255789

user output
(empty)

Error:
checking 592850, 6319
592850 6319 1
592850 6319 2
592850 6319 3
592850 6319 4
592850 6319...

Test 32

Group: 1, 4

Verdict:

input
1000 100
182415 659794
581623 510256
594984 525993
367726 938015
...

correct output
50501

user output
(empty)

Error:
checking 883906, 563422
883906 563422 1
883906 563422 2
883906 563422 3
883906 563422 4
88...

Test 33

Group: 1, 4

Verdict:

input
1000 1000
668976 422918
350791 933024
893307 88057
278098 13847
...

correct output
57897

user output
(empty)

Error:
checking 573546, 215415
573546 215415 1
573546 215415 2
573546 215415 3
573546 215415 4
57...

Test 34

Group: 1, 4

Verdict:

input
1000 1000
701742 116334
278337 368995
187245 133297
273083 369187
...

correct output
60537

user output
(empty)

Error:
checking 599683, 399987
599683 399987 1
599683 399987 2
599683 399987 3
599683 399987 4
59...

Test 35

Group: 1, 4

Verdict:

input
10 10
693836 74759
61731 520849
666762 45364
559335 979511
...

correct output
417182

user output
(empty)

Error:
checking 850818, 38631
850818 38631 1
850818 38631 2
850818 38631 3
850818 38631 4
850818...

Test 36

Group: 1, 4

Verdict:

input
1000 1000
207572 43521
513003 683552
58800 253576
16541 558695
...

correct output
69609

user output
(empty)

Error:
checking 726471, 158889
726471 158889 1
726471 158889 2
726471 158889 3
726471 158889 4
72...

Test 37

Group: 4

Verdict:

input
10000 10000
89066 605574
504488 66068
959128 348414
68004 849599
...

correct output
22936

user output
(empty)

Error:
checking 844037, 666404
844037 666404 1
844037 666404 2
844037 666404 3
844037 666404 4
84...

Test 38

Group: 4

Verdict:

input
100000 100000
20824 214259
463783 904059
603615 769692
789080 399093
...

correct output
8070

user output
(empty)

Error:
checking 504803, 448977
504803 448977 1
504803 448977 2
504803 448977 3
504803 448977 4
50...

Test 39

Group: 4

Verdict:

input
100000 100000
811424 464350
336948 946495
204883 914446
171888 431769
...

correct output
8240

user output
(empty)

Error:
checking 910396, 408397
910396 408397 1
910396 408397 2
910396 408397 3
910396 408397 4
91...

Test 40

Group: 4

Verdict:

input
100000 100000
850810 902354
292608 63461
223139 188900
197760 995048
...

correct output
7769

user output
(empty)

Error:
checking 531536, 593188
531536 593188 1
531536 593188 2
531536 593188 3
531536 593188 4
53...

Test 41

Group: 4

Verdict:

input
100000 100000
1 1
1 2
1 3
1 4
...

correct output
1899999

user output
(empty)

Error:
checking 1000000, 1000000
1000000 1000000 1
1000000 1000000 2
1000000 1000000 3
1000000 10...