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
#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);
                        ^
# 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