oj.uz

Submission #546000

# Submission time Handle Problem Language Result Execution time Memory
546000 2022-04-05T22:21:40 Z MilosMilutinovic Robots (APIO13_robots) C++14
100 / 100
 570 ms 58824 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 6 ms 9044 KB Output is correct
3 Correct 7 ms 9072 KB Output is correct
4 Correct 6 ms 9128 KB Output is correct
5 Correct 5 ms 9132 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 6 ms 9044 KB Output is correct
3 Correct 7 ms 9072 KB Output is correct
4 Correct 6 ms 9128 KB Output is correct
5 Correct 5 ms 9132 KB Output is correct
6 Correct 5 ms 9044 KB Output is correct
7 Correct 5 ms 9044 KB Output is correct
8 Correct 6 ms 9132 KB Output is correct
9 Correct 5 ms 9044 KB Output is correct
10 Correct 6 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 6 ms 9044 KB Output is correct
3 Correct 7 ms 9072 KB Output is correct
4 Correct 6 ms 9128 KB Output is correct
5 Correct 5 ms 9132 KB Output is correct
6 Correct 5 ms 9044 KB Output is correct
7 Correct 5 ms 9044 KB Output is correct
8 Correct 6 ms 9132 KB Output is correct
9 Correct 5 ms 9044 KB Output is correct
10 Correct 6 ms 9172 KB Output is correct
11 Correct 193 ms 27744 KB Output is correct
12 Correct 9 ms 12116 KB Output is correct
13 Correct 92 ms 21712 KB Output is correct
14 Correct 229 ms 28072 KB Output is correct
15 Correct 170 ms 27596 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 6 ms 9044 KB Output is correct
3 Correct 7 ms 9072 KB Output is correct
4 Correct 6 ms 9128 KB Output is correct
5 Correct 5 ms 9132 KB Output is correct
6 Correct 5 ms 9044 KB Output is correct
7 Correct 5 ms 9044 KB Output is correct
8 Correct 6 ms 9132 KB Output is correct
9 Correct 5 ms 9044 KB Output is correct
10 Correct 6 ms 9172 KB Output is correct
11 Correct 193 ms 27744 KB Output is correct
12 Correct 9 ms 12116 KB Output is correct
13 Correct 92 ms 21712 KB Output is correct
14 Correct 229 ms 28072 KB Output is correct
15 Correct 170 ms 27596 KB Output is correct
16 Correct 399 ms 57536 KB Output is correct
17 Correct 570 ms 58824 KB Output is correct
18 Correct 414 ms 58028 KB Output is correct
19 Correct 387 ms 57540 KB Output is correct
20 Correct 502 ms 58320 KB Output is correct