Submission #28651

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28651	2017-07-16T08:23:48 Z	볼빨간 승관이(#1152, sys7961, deneb2016, hyorothy)	Oriental P.A.D.A.K (FXCUP2_padak)	C++11	1 / 1	646 ms	24436 KB

padak

#include<bits/stdc++.h>
using std::pair;
using std::vector;
using pii = pair<int, int>;
bool wall[1000010];
int dist[1000010];
bool chk[1000010];
int main() {
	memset(dist, 0x3f, sizeof(dist));
	int n, m, k, b, z;
	scanf("%d%d%d%d%d", &n, &m, &k, &b, &z);
	std::queue<int> que;
	auto idx = [&](int i, int j) {return i*m + j; };
	for (int i = 0; i < k; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--; b--;
		wall[idx(a, b)] = 1;
		que.push(idx(a, b));
		dist[idx(a, b)] = 0;
	}
	const int X[] = { +1,-1,0,0 };
	const int Y[] = { 0,0,+1,-1 };
	auto inner = [&](int i, int j) {return i >= 0 && i < n && j >= 0 && j < m; };
	while (!que.empty()) {
		int p = que.front();
		que.pop();
		int x = p / m;
		int y = p%m;
		for (int k = 0; k < 4; k++) {
			int nx = x + X[k];
			int ny = y + Y[k];
			if (inner(nx, ny) && dist[idx(nx, ny)] > dist[p] + 1 && wall[idx(nx,ny)]==0) {
				dist[idx(nx, ny)] = dist[p] + 1;
				que.push(idx(nx, ny));
			}
		}
	}
	vector<pii> order;
	for (int i = 0; i < n*m; i++) {
		order.push_back({ dist[i],i });
	}
	std::sort(order.begin(), order.end());
	int ans1 = 0, ans2 = 0;
	int t = 1;
	int p = 0;
	while (p < n*m) {
		while (p<n*m && order[p].first < t)p++;
		for (int i = 0; i < z; i++) {
			if (p < n*m) {
				ans1++;
				p++;
			}
		}
		t++;
	}
	std::reverse(order.begin(), order.end());
	t = 1;
	p = 0;
	while (p < n*m) {
		while (p<n*m && order[p].first < t)p++;
		for (int i = 0; i < z; i++) {
			if (p < n*m && order[p].first>=t) {
				ans2++;
				p++;
			}
		}
		t++;
	}
	printf("%d %d", ans2, ans1);

}

Compilation message

padak.cpp: In function 'int main()':
padak.cpp:11:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &n, &m, &k, &b, &z);
                                         ^
padak.cpp:16:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	7884 KB	Output is correct
2	Correct	0 ms	8024 KB	Output is correct
3	Correct	153 ms	20256 KB	Output is correct
4	Correct	156 ms	20260 KB	Output is correct
5	Correct	176 ms	20260 KB	Output is correct
6	Correct	136 ms	20256 KB	Output is correct
7	Correct	143 ms	20256 KB	Output is correct
8	Correct	79 ms	20256 KB	Output is correct
9	Correct	133 ms	20256 KB	Output is correct
10	Correct	156 ms	20268 KB	Output is correct
11	Correct	173 ms	20300 KB	Output is correct
12	Correct	169 ms	20280 KB	Output is correct
13	Correct	139 ms	20260 KB	Output is correct
14	Correct	163 ms	20256 KB	Output is correct
15	Correct	136 ms	20256 KB	Output is correct
16	Correct	123 ms	20256 KB	Output is correct
17	Correct	169 ms	20312 KB	Output is correct
18	Correct	193 ms	20584 KB	Output is correct
19	Correct	173 ms	20312 KB	Output is correct
20	Correct	169 ms	20300 KB	Output is correct
21	Correct	189 ms	20648 KB	Output is correct
22	Correct	146 ms	20256 KB	Output is correct
23	Correct	166 ms	20280 KB	Output is correct
24	Correct	599 ms	24436 KB	Output is correct
25	Correct	579 ms	24436 KB	Output is correct
26	Correct	349 ms	24436 KB	Output is correct
27	Correct	489 ms	24436 KB	Output is correct
28	Correct	526 ms	24436 KB	Output is correct
29	Correct	646 ms	20472 KB	Output is correct
30	Correct	539 ms	24436 KB	Output is correct
31	Correct	133 ms	20260 KB	Output is correct
32	Correct	63 ms	20256 KB	Output is correct