Submission #965218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
965218	2024-04-18T08:26:17 Z	Gromp15	Cell Automaton (JOI23_cell)	C++17	16 / 100	734 ms	140872 KB

cell

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int N = 2100;
void test_case() {
	int n, Q; cin >> n >> Q;
	queue<ar<int, 2>> q;
	vector<vector<int>> dist(2*N, vector<int>(2*N, 1e9));
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		x += N, y += N;
		dist[x][y] = 0;
		q.push({x, y});
	}
	const int dx[]{0, 1, 0, -1}, dy[]{1, 0, -1, 0};
	while (q.size()) {
		auto [x, y] = q.front(); q.pop();
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d], ny = y + dy[d];
			if (nx >= 0 && ny >= 0 && nx < 2*N && ny < 2*N && ckmin(dist[nx][ny], dist[x][y] + 1)) {
				q.push({nx, ny});
			}
		}
	}
	const int T = 1000;
	vector<int> ans(T + 1);
	for (int i = 0; i < 2*N; i++) {
		for (int j = 0; j < 2*N; j++) {
			if (dist[i][j] <= T) {
				ans[dist[i][j]]++;
			}
		}
	}
	while (Q--) {
		int t; cin >> t; cout << ans[t] << '\n';
	}
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	628 ms	69716 KB	Output is correct
2	Correct	676 ms	69812 KB	Output is correct
3	Correct	722 ms	69932 KB	Output is correct
4	Correct	580 ms	69712 KB	Output is correct
5	Correct	643 ms	69716 KB	Output is correct
6	Correct	649 ms	69720 KB	Output is correct
7	Correct	710 ms	69716 KB	Output is correct
8	Correct	711 ms	69728 KB	Output is correct
9	Correct	722 ms	70172 KB	Output is correct
10	Correct	710 ms	69928 KB	Output is correct
11	Correct	707 ms	69672 KB	Output is correct
12	Correct	588 ms	69712 KB	Output is correct
13	Correct	679 ms	69732 KB	Output is correct
14	Correct	656 ms	69716 KB	Output is correct
15	Correct	672 ms	69724 KB	Output is correct
16	Correct	679 ms	69936 KB	Output is correct
17	Correct	596 ms	69716 KB	Output is correct
18	Correct	662 ms	69968 KB	Output is correct
19	Correct	623 ms	69716 KB	Output is correct
20	Correct	697 ms	69940 KB	Output is correct
21	Correct	629 ms	69920 KB	Output is correct
22	Correct	677 ms	69716 KB	Output is correct
23	Correct	704 ms	69712 KB	Output is correct
24	Correct	707 ms	69704 KB	Output is correct
25	Correct	600 ms	69720 KB	Output is correct
26	Correct	734 ms	69720 KB	Output is correct
27	Correct	706 ms	69712 KB	Output is correct
28	Correct	707 ms	69720 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	628 ms	69716 KB	Output is correct
2	Correct	676 ms	69812 KB	Output is correct
3	Correct	722 ms	69932 KB	Output is correct
4	Correct	580 ms	69712 KB	Output is correct
5	Correct	643 ms	69716 KB	Output is correct
6	Correct	649 ms	69720 KB	Output is correct
7	Correct	710 ms	69716 KB	Output is correct
8	Correct	711 ms	69728 KB	Output is correct
9	Correct	722 ms	70172 KB	Output is correct
10	Correct	710 ms	69928 KB	Output is correct
11	Correct	707 ms	69672 KB	Output is correct
12	Correct	588 ms	69712 KB	Output is correct
13	Correct	679 ms	69732 KB	Output is correct
14	Correct	656 ms	69716 KB	Output is correct
15	Correct	672 ms	69724 KB	Output is correct
16	Correct	679 ms	69936 KB	Output is correct
17	Correct	596 ms	69716 KB	Output is correct
18	Correct	662 ms	69968 KB	Output is correct
19	Correct	623 ms	69716 KB	Output is correct
20	Correct	697 ms	69940 KB	Output is correct
21	Correct	629 ms	69920 KB	Output is correct
22	Correct	677 ms	69716 KB	Output is correct
23	Correct	704 ms	69712 KB	Output is correct
24	Correct	707 ms	69704 KB	Output is correct
25	Correct	600 ms	69720 KB	Output is correct
26	Correct	734 ms	69720 KB	Output is correct
27	Correct	706 ms	69712 KB	Output is correct
28	Correct	707 ms	69720 KB	Output is correct
29	Correct	676 ms	69696 KB	Output is correct
30	Correct	700 ms	69712 KB	Output is correct
31	Correct	663 ms	69716 KB	Output is correct
32	Correct	630 ms	72996 KB	Output is correct
33	Correct	678 ms	69716 KB	Output is correct
34	Correct	655 ms	69968 KB	Output is correct
35	Correct	613 ms	69716 KB	Output is correct
36	Correct	603 ms	69944 KB	Output is correct
37	Correct	624 ms	69944 KB	Output is correct
38	Correct	642 ms	69964 KB	Output is correct
39	Correct	638 ms	70652 KB	Output is correct
40	Correct	701 ms	72608 KB	Output is correct

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	95 ms	140712 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	95 ms	140712 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	100 ms	140872 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	100 ms	140872 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	628 ms	69716 KB	Output is correct
2	Correct	676 ms	69812 KB	Output is correct
3	Correct	722 ms	69932 KB	Output is correct
4	Correct	580 ms	69712 KB	Output is correct
5	Correct	643 ms	69716 KB	Output is correct
6	Correct	649 ms	69720 KB	Output is correct
7	Correct	710 ms	69716 KB	Output is correct
8	Correct	711 ms	69728 KB	Output is correct
9	Correct	722 ms	70172 KB	Output is correct
10	Correct	710 ms	69928 KB	Output is correct
11	Correct	707 ms	69672 KB	Output is correct
12	Correct	588 ms	69712 KB	Output is correct
13	Correct	679 ms	69732 KB	Output is correct
14	Correct	656 ms	69716 KB	Output is correct
15	Correct	672 ms	69724 KB	Output is correct
16	Correct	679 ms	69936 KB	Output is correct
17	Correct	596 ms	69716 KB	Output is correct
18	Correct	662 ms	69968 KB	Output is correct
19	Correct	623 ms	69716 KB	Output is correct
20	Correct	697 ms	69940 KB	Output is correct
21	Correct	629 ms	69920 KB	Output is correct
22	Correct	677 ms	69716 KB	Output is correct
23	Correct	704 ms	69712 KB	Output is correct
24	Correct	707 ms	69704 KB	Output is correct
25	Correct	600 ms	69720 KB	Output is correct
26	Correct	734 ms	69720 KB	Output is correct
27	Correct	706 ms	69712 KB	Output is correct
28	Correct	707 ms	69720 KB	Output is correct
29	Correct	676 ms	69696 KB	Output is correct
30	Correct	700 ms	69712 KB	Output is correct
31	Correct	663 ms	69716 KB	Output is correct
32	Correct	630 ms	72996 KB	Output is correct
33	Correct	678 ms	69716 KB	Output is correct
34	Correct	655 ms	69968 KB	Output is correct
35	Correct	613 ms	69716 KB	Output is correct
36	Correct	603 ms	69944 KB	Output is correct
37	Correct	624 ms	69944 KB	Output is correct
38	Correct	642 ms	69964 KB	Output is correct
39	Correct	638 ms	70652 KB	Output is correct
40	Correct	701 ms	72608 KB	Output is correct
41	Runtime error	95 ms	140712 KB	Execution killed with signal 11
42	Halted	0 ms	0 KB	-