QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207225#5818. MacaronTerryjoy20 34ms9288kbC++142.3kb2023-10-08 11:49:002023-10-08 11:49:01

Judging History

你现在查看的是最新测评结果

  • [2023-10-08 11:49:01]
  • 评测
  • 测评结果:20
  • 用时:34ms
  • 内存:9288kb
  • [2023-10-08 11:49:00]
  • 提交

answer

#include <bits/stdc++.h>
using i64 = long long;

const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
#define pii std::pair<int, int>
#define ppi std::pair<pii, pii>
#define x first
#define y second

int dis(pii a, pii b) {
    auto x = a.x - b.x, y = a.y - b.y;
    return x * x + y * y;
}
bool vis[2000][2000]; 
signed main() {
    std::ios_base::sync_with_stdio(0), std::cin.tie(0);

    int n, m;
    std::cin >> n >> m;

    auto ok = [&](int x, int y) {
        return 0 <= x and x <= n + 1 and 0 <= y and y <= m + 1;
    };

    int r2;
    std::cin >> r2;

    int sx, sy, k;
    std::cin >> sx >> sy >> k;

//    std::vector vis(n + 2, std::vector<bool>(m + 2, false));

    std::queue<ppi> q;

    for (int i = 1; i <= n; i++)
        for (int j : {0, m + 1})
            q.push({{i, j}, {i, j}});
    for (int i : {0, n + 1})
        for (int j = 1; j <= m; j++)
            q.push({{i, j}, {i, j}});
    q.push({{0, 0}, {0, 0}});
    q.push({{0, m + 1}, {0, m + 1}});
    q.push({{n + 1, 0}, {n + 1, 0}});
    q.push({{n + 1, m + 1}, {n + 1, m + 1}});
    for (int x, y, i = 1; i <= k; i++) {
        std::cin >> x >> y;
        q.push({{x, y}, {x, y}});
    }

    // bfs the vis
    while (!q.empty()) {
        auto [cen, p] = q.front();

        q.pop();

        if (ok(p.x, p.y))
            vis[p.x][p.y] = true;

        for (int k = 0; k < 8; k++) {

            int X = p.x + dx[k], Y = p.y + dy[k];
            if (ok(X, Y) and vis[X][Y] == false and dis(cen, {X, Y}) < r2) {
                vis[X][Y] = true;
                q.push({cen, {X, Y}});
            }
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++)
    //         std::cerr << (vis[i][j] ? '#' : '.');
    //     std::cerr << '\n';
    // }

    int ans = 0;
    std::queue<pii> Q;
    Q.push({sx, sy});
    vis[sx][sy] = true;
    // bfs the ans
    while (!Q.empty()) {

        auto [x, y] = Q.front();
        Q.pop();
        ans++;

        for (int k = 0; k < 8; k++) {
            int X = x + dx[k], Y = y + dy[k];
            if (ok(X, Y) and vis[X][Y] == false) {
                vis[X][Y] = true;
                Q.push({X, Y});
            }
        }
    }
    std::cout << ans;
}

详细

Test #1:

score: 10
Accepted
time: 0ms
memory: 3552kb

input:

11 11
5
9 7
4
1 10
1 11
8 3
8 4

output:

37

result:

ok single line: '37'

Test #2:

score: 0
Wrong Answer
time: 16ms
memory: 5908kb

input:

999 999
3000
340 211
25
230 432
513 610
514 610
360 56
360 55
474 319
474 318
687 476
687 477
204 142
205 142
206 142
207 142
244 511
243 511
242 511
241 511
32 652
32 653
32 654
32 655
197 976
539 579
540 579
540 578

output:

764436

result:

wrong answer 1st lines differ - expected: '724629', found: '764436'

Test #3:

score: 0
Wrong Answer
time: 15ms
memory: 5736kb

input:

1000 1000
5000
748 173
24
944 654
943 654
944 653
942 654
941 654
941 655
942 655
940 655
939 655
938 655
939 656
938 656
635 128
636 128
634 128
635 127
637 128
633 128
632 128
633 127
631 128
630 128
629 128
628 128

output:

762922

result:

wrong answer 1st lines differ - expected: '716645', found: '762922'

Test #4:

score: 0
Wrong Answer
time: 14ms
memory: 5672kb

input:

1000 1000
10000
668 126
30
9 589
39 505
165 527
185 25
211 383
231 699
235 849
291 839
317 955
319 627
355 79
355 117
365 521
447 253
473 721
515 161
517 157
587 465
627 849
641 515
729 893
775 81
783 583
813 1
839 699
869 215
931 365
937 975
941 47
965 249

output:

210504

result:

wrong answer 1st lines differ - expected: '192418', found: '210504'

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 3988kb

input:

50 50
30
36 40
11
50 41
29 16
31 23
48 9
27 22
8 33
9 33
1 40
3 39
27 21
29 30

output:

1201

result:

wrong answer 1st lines differ - expected: '1200', found: '1201'

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 3856kb

input:

100 100
300
69 24
17
32 34
33 34
31 34
40 55
32 10
98 77
97 77
96 77
81 71
19 69
87 66
88 66
88 67
100 38
100 37
19 89
13 48

output:

1994

result:

wrong answer 1st lines differ - expected: '1730', found: '1994'

Test #7:

score: 0
Wrong Answer
time: 16ms
memory: 5972kb

input:

1000 1000
5000
845 228
41
13 132
12 132
13 133
13 131
11 132
12 133
14 131
11 131
908 888
907 888
401 736
350 495
350 494
349 494
348 494
349 493
348 495
350 493
347 495
348 496
351 493
349 496
348 497
351 492
351 491
859 937
295 732
295 733
151 720
152 720
151 721
152 721
151 722
37 291
675 123
676...

output:

687258

result:

wrong answer 1st lines differ - expected: '646861', found: '687258'

Test #8:

score: 0
Wrong Answer
time: 12ms
memory: 5844kb

input:

1000 1000
10000
845 168
7949
901 901
901 902
901 903
901 904
901 905
901 906
901 909
901 911
901 912
901 913
901 914
901 915
901 916
901 917
901 918
901 919
901 920
901 921
901 923
901 924
901 925
901 926
901 927
901 928
901 930
901 935
901 936
901 938
901 939
901 940
901 942
901 943
901 945
901 946...

output:

709205

result:

wrong answer 1st lines differ - expected: '635255', found: '709205'

Test #9:

score: 10
Accepted
time: 34ms
memory: 9288kb

input:

1000 1000
1
19 587
249999
1 1
1 3
1 5
1 7
1 9
1 11
1 13
1 15
1 17
1 19
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
1 37
1 39
1 41
1 43
1 45
1 47
1 49
1 51
1 53
1 55
1 57
1 59
1 61
1 63
1 65
1 67
1 69
1 71
1 73
1 75
1 77
1 79
1 81
1 83
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
1 101
1 103
1 105
1 107
1 109...

output:

750001

result:

ok single line: '750001'

Test #10:

score: 0
Wrong Answer
time: 14ms
memory: 5672kb

input:

1000 1000
111012
587 619
0

output:

266256

result:

wrong answer 1st lines differ - expected: '111556', found: '266256'