답안 #831261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831261	2023-08-20T03:06:47 Z	pavement	Cell Automaton (JOI23_cell)	C++17	16 / 100	2485 ms	511324 KB

cell

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

using ii = pair<int, int>;

const int D = 2000;

int N, Q, X[100005], Y[100005], dist[4 * D + 5][4 * D + 5], dr[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dc[] = {-1, 0, 1, -1, 1, -1, 0, 1}, ans[4000005];
queue<ii> qu;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i];
		int p = X[i] + Y[i], q = X[i] - Y[i];
		X[i] = p;
		Y[i] = q;
		X[i] += 2 * D;
		Y[i] += 2 * D;
	}
	for (int i = 0; i <= 4 * D; i++) {
		for (int j = 0; j <= 4 * D; j++) {
			dist[i][j] = (int)1e9;
		}
	}
	for (int i = 1; i <= N; i++) {
		dist[X[i]][Y[i]] = 0;
		qu.emplace(X[i], Y[i]);
	}
	while (!qu.empty()) {
		auto [r, c] = qu.front();
		qu.pop();
		for (int k = 0; k < 8; k++) {
			int nr = r + dr[k], nc = c + dc[k];
			if (0 <= nr && nr <= 4 * D && 0 <= nc && nc <= 4 * D) {
				if (dist[nr][nc] > dist[r][c] + 1) {
					dist[nr][nc] = dist[r][c] + 1;
					qu.emplace(nr, nc);
				}
			}
		}
	}
	for (int i = 0; i <= 4 * D; i++) {
		for (int j = 0; j <= 4 * D; j++) {
			if ((i + j) % 2 == 0) {
				ans[dist[i][j]]++;
			}
		}
	}
	for (int i = 1, t; i <= Q; i++) {
		cin >> t;
		cout << ans[t] << '\n';
	}
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2057 ms	251272 KB	Output is correct
2	Correct	2176 ms	251356 KB	Output is correct
3	Correct	2070 ms	251372 KB	Output is correct
4	Correct	2138 ms	251268 KB	Output is correct
5	Correct	2100 ms	251384 KB	Output is correct
6	Correct	2110 ms	251260 KB	Output is correct
7	Correct	2110 ms	251372 KB	Output is correct
8	Correct	2076 ms	251332 KB	Output is correct
9	Correct	2133 ms	251316 KB	Output is correct
10	Correct	2045 ms	251240 KB	Output is correct
11	Correct	2176 ms	251320 KB	Output is correct
12	Correct	2165 ms	251264 KB	Output is correct
13	Correct	2204 ms	251300 KB	Output is correct
14	Correct	2102 ms	251256 KB	Output is correct
15	Correct	2083 ms	251272 KB	Output is correct
16	Correct	2260 ms	251284 KB	Output is correct
17	Correct	2090 ms	251236 KB	Output is correct
18	Correct	2112 ms	251312 KB	Output is correct
19	Correct	2151 ms	251284 KB	Output is correct
20	Correct	2173 ms	251284 KB	Output is correct
21	Correct	2278 ms	251376 KB	Output is correct
22	Correct	2332 ms	251372 KB	Output is correct
23	Correct	2122 ms	251268 KB	Output is correct
24	Correct	2126 ms	251232 KB	Output is correct
25	Correct	2100 ms	251364 KB	Output is correct
26	Correct	2119 ms	251280 KB	Output is correct
27	Correct	2102 ms	251376 KB	Output is correct
28	Correct	2145 ms	251200 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2057 ms	251272 KB	Output is correct
2	Correct	2176 ms	251356 KB	Output is correct
3	Correct	2070 ms	251372 KB	Output is correct
4	Correct	2138 ms	251268 KB	Output is correct
5	Correct	2100 ms	251384 KB	Output is correct
6	Correct	2110 ms	251260 KB	Output is correct
7	Correct	2110 ms	251372 KB	Output is correct
8	Correct	2076 ms	251332 KB	Output is correct
9	Correct	2133 ms	251316 KB	Output is correct
10	Correct	2045 ms	251240 KB	Output is correct
11	Correct	2176 ms	251320 KB	Output is correct
12	Correct	2165 ms	251264 KB	Output is correct
13	Correct	2204 ms	251300 KB	Output is correct
14	Correct	2102 ms	251256 KB	Output is correct
15	Correct	2083 ms	251272 KB	Output is correct
16	Correct	2260 ms	251284 KB	Output is correct
17	Correct	2090 ms	251236 KB	Output is correct
18	Correct	2112 ms	251312 KB	Output is correct
19	Correct	2151 ms	251284 KB	Output is correct
20	Correct	2173 ms	251284 KB	Output is correct
21	Correct	2278 ms	251376 KB	Output is correct
22	Correct	2332 ms	251372 KB	Output is correct
23	Correct	2122 ms	251268 KB	Output is correct
24	Correct	2126 ms	251232 KB	Output is correct
25	Correct	2100 ms	251364 KB	Output is correct
26	Correct	2119 ms	251280 KB	Output is correct
27	Correct	2102 ms	251376 KB	Output is correct
28	Correct	2145 ms	251200 KB	Output is correct
29	Correct	2159 ms	251296 KB	Output is correct
30	Correct	2005 ms	251292 KB	Output is correct
31	Correct	1966 ms	251292 KB	Output is correct
32	Correct	2213 ms	257168 KB	Output is correct
33	Correct	2295 ms	251444 KB	Output is correct
34	Correct	2431 ms	251256 KB	Output is correct
35	Correct	2485 ms	251340 KB	Output is correct
36	Correct	2043 ms	251244 KB	Output is correct
37	Correct	2025 ms	251264 KB	Output is correct
38	Correct	2203 ms	251616 KB	Output is correct
39	Correct	2146 ms	253104 KB	Output is correct
40	Correct	2300 ms	258016 KB	Output is correct

Subtask #3

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	339 ms	511324 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	339 ms	511324 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2233 ms	509248 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2233 ms	509248 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2057 ms	251272 KB	Output is correct
2	Correct	2176 ms	251356 KB	Output is correct
3	Correct	2070 ms	251372 KB	Output is correct
4	Correct	2138 ms	251268 KB	Output is correct
5	Correct	2100 ms	251384 KB	Output is correct
6	Correct	2110 ms	251260 KB	Output is correct
7	Correct	2110 ms	251372 KB	Output is correct
8	Correct	2076 ms	251332 KB	Output is correct
9	Correct	2133 ms	251316 KB	Output is correct
10	Correct	2045 ms	251240 KB	Output is correct
11	Correct	2176 ms	251320 KB	Output is correct
12	Correct	2165 ms	251264 KB	Output is correct
13	Correct	2204 ms	251300 KB	Output is correct
14	Correct	2102 ms	251256 KB	Output is correct
15	Correct	2083 ms	251272 KB	Output is correct
16	Correct	2260 ms	251284 KB	Output is correct
17	Correct	2090 ms	251236 KB	Output is correct
18	Correct	2112 ms	251312 KB	Output is correct
19	Correct	2151 ms	251284 KB	Output is correct
20	Correct	2173 ms	251284 KB	Output is correct
21	Correct	2278 ms	251376 KB	Output is correct
22	Correct	2332 ms	251372 KB	Output is correct
23	Correct	2122 ms	251268 KB	Output is correct
24	Correct	2126 ms	251232 KB	Output is correct
25	Correct	2100 ms	251364 KB	Output is correct
26	Correct	2119 ms	251280 KB	Output is correct
27	Correct	2102 ms	251376 KB	Output is correct
28	Correct	2145 ms	251200 KB	Output is correct
29	Correct	2159 ms	251296 KB	Output is correct
30	Correct	2005 ms	251292 KB	Output is correct
31	Correct	1966 ms	251292 KB	Output is correct
32	Correct	2213 ms	257168 KB	Output is correct
33	Correct	2295 ms	251444 KB	Output is correct
34	Correct	2431 ms	251256 KB	Output is correct
35	Correct	2485 ms	251340 KB	Output is correct
36	Correct	2043 ms	251244 KB	Output is correct
37	Correct	2025 ms	251264 KB	Output is correct
38	Correct	2203 ms	251616 KB	Output is correct
39	Correct	2146 ms	253104 KB	Output is correct
40	Correct	2300 ms	258016 KB	Output is correct
41	Runtime error	339 ms	511324 KB	Execution killed with signal 11
42	Halted	0 ms	0 KB	-