oj.uz

Submission #546001

# Submission time Handle Problem Language Result Execution time Memory
546001 2022-04-05T22:22:25 Z MilosMilutinovic Robots (APIO13_robots) C++14
100 / 100
 549 ms 58648 KB 
#include <ctype.h>
#include <stdio.h>
#include <string.h>

#define N	500
#define M	500
#define K	9
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, 1, 0, -1 };

char cc[N][M];
int n, m, dp[N][N][4];

int solve(int i, int j, int h) {
	if (dp[i][j][h] == -1) {
		int h_, i_, j_;

		dp[i][j][h] = -2;
 		if (cc[i][j] == 'C')
			h_ = (h + 1) % 4;
		else if (cc[i][j] == 'A')
			h_ = (h + 3) % 4;
		else
			h_ = h;
		i_ = i + di[h_], j_ = j + dj[h_];
		if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] != 'x')
			dp[i][j][h] = solve(i_, j_, h_);
		else
			dp[i][j][h] = i * m + j;
	}
	return dp[i][j][h];
}

void sort(int *aa, int *ii, int n, int n_) {
	static int jj[N * M], kk[N * M * K];
	int i;

	memset(kk, 0, N * M * K * sizeof *kk);
	for (i = 0; i < n; i++)
		kk[aa[ii[i]] + 1]++;
	for (i = 1; i <= n_; i++)
		kk[i] += kk[i - 1];
	for (i = 0; i < n; i++)
		jj[kk[aa[ii[i]]]++] = ii[i];
	memcpy(ii, jj, n * sizeof *jj);
}

int main() {
	static int dd[K][K][N * M], qu1[N * M], qu2[N * M];
	int k, i, j, h, l, r, ij, head1, cnt1, head2, cnt2, ans;

	scanf("%d%d%d", &k, &m, &n);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			for (h = 0; h < 4; h++)
				dp[i][j][h] = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			for (h = 0; h < 4; h++)
				dp[i][j][h] = (cc[i][j] == 'x' ? -2 : solve(i, j, h));
	for (l = k - 1; l >= 0; l--) {
		for (r = l; r < k; r++) {
			int *dd_ = dd[l][r], cnt;

			memset(dd_, INF, n * m * sizeof *dd_);
			head1 = cnt1 = head2 = cnt2 = 0;
			if (l == r) {
				for (i = 0; i < n; i++)
					for (j = 0; j < m; j++)
						if (cc[i][j] == l + '1') {
							ij = i * m + j;
							dd_[ij] = 0, qu1[cnt1++] = ij;
						}
			} else
				for (i = 0; i < n; i++)
					for (j = 0; j < m; j++) {
						ij = i * m + j;
						for (h = l; h < r; h++)
							dd_[ij] = min(dd_[ij], dd[l][h][ij] + dd[h + 1][r][ij]);
						if (dd_[ij] != INF)
							qu1[cnt1++] = ij;
					}
			sort(dd_, qu1, cnt1, n * m * k);
			while (cnt1 || cnt2) {
				int d;

				ij = !cnt2 || cnt1 && dd_[qu1[head1]] < dd_[qu2[head2]] ? qu1[cnt1--, head1++] : qu2[cnt2--, head2++], i = ij / m, j = ij % m, d = dd_[ij] + 1;
				for (h = 0; h < 4; h++) {
					int ij_ = dp[i][j][h];

					if (ij_ != -2 && dd_[ij_] > d)
						dd_[ij_] = d, qu2[head2 + cnt2++] = ij_;
				}
			}
		}
	}
	ans = INF;
	for(i = 0; i < n; i++)
		for(j = 0; j < m; j++)
			ans = min(ans, dd[0][k - 1][i * m + j]);
	if (ans == INF)
		ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:93:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   93 |     ij = !cnt2 || cnt1 && dd_[qu1[head1]] < dd_[qu2[head2]] ? qu1[cnt1--, head1++] : qu2[cnt2--, head2++], i = ij / m, j = ij % m, d = dd_[ij] + 1;
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:69:25: warning: unused variable 'cnt' [-Wunused-variable]
   69 |    int *dd_ = dd[l][r], cnt;
      |                         ^~~
robots.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d%d%d", &k, &m, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%s", cc[i]);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9044 KB Output is correct
2 Correct 5 ms 9044 KB Output is correct
3 Correct 5 ms 9044 KB Output is correct
4 Correct 5 ms 9172 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9044 KB Output is correct
2 Correct 5 ms 9044 KB Output is correct
3 Correct 5 ms 9044 KB Output is correct
4 Correct 5 ms 9172 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 6 ms 9044 KB Output is correct
7 Correct 6 ms 9044 KB Output is correct
8 Correct 6 ms 9136 KB Output is correct
9 Correct 5 ms 9044 KB Output is correct
10 Correct 5 ms 9172 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9044 KB Output is correct
2 Correct 5 ms 9044 KB Output is correct
3 Correct 5 ms 9044 KB Output is correct
4 Correct 5 ms 9172 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 6 ms 9044 KB Output is correct
7 Correct 6 ms 9044 KB Output is correct
8 Correct 6 ms 9136 KB Output is correct
9 Correct 5 ms 9044 KB Output is correct
10 Correct 5 ms 9172 KB Output is correct
11 Correct 175 ms 27644 KB Output is correct
12 Correct 8 ms 11988 KB Output is correct
13 Correct 84 ms 21568 KB Output is correct
14 Correct 223 ms 27764 KB Output is correct
15 Correct 173 ms 27464 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9044 KB Output is correct
2 Correct 5 ms 9044 KB Output is correct
3 Correct 5 ms 9044 KB Output is correct
4 Correct 5 ms 9172 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 6 ms 9044 KB Output is correct
7 Correct 6 ms 9044 KB Output is correct
8 Correct 6 ms 9136 KB Output is correct
9 Correct 5 ms 9044 KB Output is correct
10 Correct 5 ms 9172 KB Output is correct
11 Correct 175 ms 27644 KB Output is correct
12 Correct 8 ms 11988 KB Output is correct
13 Correct 84 ms 21568 KB Output is correct
14 Correct 223 ms 27764 KB Output is correct
15 Correct 173 ms 27464 KB Output is correct
16 Correct 380 ms 57348 KB Output is correct
17 Correct 549 ms 58648 KB Output is correct
18 Correct 401 ms 57804 KB Output is correct
19 Correct 375 ms 57376 KB Output is correct
20 Correct 469 ms 58000 KB Output is correct