QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93844 | #5818. Macaron | nhuang685 | 10 | 151ms | 112712kb | C++17 | 2.7kb | 2023-04-03 08:18:45 | 2023-04-03 08:18:50 |
Judging History
answer
/**
* @author nhuang685
* @date 2023-04-02 19:42:00
*/
#include <bits/stdc++.h>
using namespace std;
const array<int, 4> dx{-1, 0, 1, 0}, dy{0, 1, 0, -1};
int main() {
ios::sync_with_stdio(false);
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
// freopen("log.txt", "w", stderr);
#else
cin.tie(nullptr);
#endif
int n, m;
cin >> n >> m;
int r2;
cin >> r2;
pair<int, int> s;
cin >> s.first >> s.second;
int k;
cin >> k;
vector<vector<int>> grid(n + 1, vector<int>(n + 1, (int)4e18));
for (int i = 0; i < k; ++i) {
int x, y;
cin >> x >> y;
// x--;
// y--;
grid[x][y] = 0;
}
auto bfs = [&](queue<pair<int, int>> q) {
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int a = x + dx[d], b = y + dy[d];
if (a > 0 && a <= n && b > 0 && b <= n && grid[a][b] > grid[x][y] + 1) {
grid[a][b] = grid[x][y] + 1;
q.push({a, b});
}
}
}
};
for (int i = 1; i <= n; ++i) {
queue<pair<int, int>> q;
for (int j = 1; j <= n; ++j) {
if (grid[i][j] == 0) q.push({i, j});
}
bfs(q);
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= n; ++j) {
// cout << grid[i][j] << '\t';
// }
// cout << '\n';
// }
auto sqt = [](int a) {
int l = 0, r = a;
while (l < r) {
int mid = (l + r) / 2;
if (mid * mid >= a)
r = mid;
else
l = mid + 1;
}
return l;
};
vector<vector<int>> over(n + 2, vector<int>(n + 2));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (r2 <= grid[i][j] * grid[i][j]) continue;
int d = sqt(r2 - grid[i][j] * grid[i][j]);
// i - d + 1, i + d - 1
over[max(1, i - d + 1)][j] += 1;
over[min(n + 1, i + d)][j] -= 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
over[i][j] += over[i - 1][j];
}
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= n; ++j) {
// cout << over[i][j] << '\t';
// }
// cout << '\n';
// }
vector<vector<bool>> v(n + 1, vector<bool>(n + 1));
auto dfs = [&](auto &self, int a, int b) -> int {
v[a][b] = true;
int ans = 1;
for (int d = 0; d < 4; ++d) {
int i = a + dx[d], j = b + dy[d];
if (i * i >= r2 && (n - i + 1) * (n - i + 1) >= r2 && j * j >= r2 &&
(n - j + 1) * (n - j + 1) >= r2 && over[i][j] == 0 && !v[i][j])
ans += self(self, i, j);
}
return ans;
};
cout << dfs(dfs, s.first, s.second) << '\n';
}
詳細信息
Test #1:
score: 10
Accepted
time: 2ms
memory: 3388kb
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: 104ms
memory: 103968kb
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:
714979
result:
wrong answer 1st lines differ - expected: '724629', found: '714979'
Test #3:
score: 0
Wrong Answer
time: 111ms
memory: 112712kb
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:
713529
result:
wrong answer 1st lines differ - expected: '716645', found: '713529'
Test #4:
score: 0
Wrong Answer
time: 111ms
memory: 21948kb
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:
123887
result:
wrong answer 1st lines differ - expected: '192418', found: '123887'
Test #5:
score: 0
Wrong Answer
time: 2ms
memory: 3520kb
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:
1159
result:
wrong answer 1st lines differ - expected: '1200', found: '1159'
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 3652kb
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:
1460
result:
wrong answer 1st lines differ - expected: '1730', found: '1460'
Test #7:
score: 0
Wrong Answer
time: 151ms
memory: 99784kb
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:
636755
result:
wrong answer 1st lines differ - expected: '646861', found: '636755'
Test #8:
score: 0
Wrong Answer
time: 92ms
memory: 110268kb
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:
634153
result:
wrong answer 1st lines differ - expected: '635255', found: '634153'
Test #9:
score: 0
Time Limit Exceeded
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:
result:
Test #10:
score: 0
Wrong Answer
time: 26ms
memory: 11240kb
input:
1000 1000 111012 587 619 0
output:
1
result:
wrong answer 1st lines differ - expected: '111556', found: '1'