oj.uz

Submission #43312

# Submission time Handle Problem Language Result Execution time Memory
43312 2018-03-13T12:34:19 Z mohammad_kilani Robots (APIO13_robots) C++14
30 / 100
 1500 ms 163840 KB 
#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;
const int N = 510, MAX_COST = 500 * 75 * 9 + 2, oo = 2000000000;
char grid[N][N];
int n, m, k, dp[60][N][N], hsh[10][10], hashcnt = 0 , sr ,sc , nr , nc;
pair<int, int> go[4][N][N];
int dr[4] = { 0,1,0,-1 };
int dc[4] = { 1,0,-1,0 };

struct S {
	int r, c, low, high;
	S(int a, int b, int e, int d) { r = a, c = b, low = e, high = d; }
};

vector< S > pq[MAX_COST];

inline bool cangoto(int r, int c) {
	return (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != 'x');
}

inline void make(int r, int c, int d) {
	sr = r, sc = c;
	while (cangoto(r, c)) {
		go[d][r][c] = make_pair(sr, sc);
		if (grid[r][c] == 'C') d--; else if (grid[r][c] == 'A') d++;
		if (d == 4) d = 0;
		if (d == -1) d = 3;
		r += dr[d];
		c += dc[d];
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof(dp));
	for (int i = 1;i <= 9;i++) {
		for (int j = i;j <= 9;j++) {
			hsh[i][j] = hashcnt++;
		}
	}
	memset(go, -1, sizeof(go));
	scanf("%d%d%d", &k, &m, &n);
	for (int i = 0;i < n;i++)
		scanf("%s", grid[i]);
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (grid[i][j] >= '1' && grid[i][j] <= '9') {
				pq[0].push_back(S(i, j, grid[i][j] - '0', grid[i][j] - '0'));
			}
			if (grid[i][j] == 'x') continue;
			for (int k = 0;k < 4;k++) {
				nr = i + dr[k];
				nc = j + dc[k];
				if (cangoto(nr, nc) == false) {
					make(i, j, (k + 2) % 4);
				}
			}
		}
	}
	int low, high, r, c, nr, nc, ans = oo;
	for (int i = 0;i < MAX_COST - 1;i++) {
		for (int j = 0;j < (int)pq[i].size();j++) {
			r = pq[i][j].r;
			c = pq[i][j].c;
			low = pq[i][j].low;
			high = pq[i][j].high;
			if (dp[hsh[low][high]][r][c] != -1)
				continue;
			if (low == 1 && high == k)
				ans = min(ans, i);
			dp[hsh[low][high]][r][c] = i;
			for (int j = 0;j < 4;j++) {
				nr = go[j][r][c].first;
				nc = go[j][r][c].second;
				if (dp[hsh[low][high]][nr][nc] == -1)
					pq[i + 1].push_back(S(nr, nc, low, high));
			}
			for (int j = low - 1;j >= 1;j--) {
				if (dp[hsh[j][low - 1]][r][c] != -1 && dp[hsh[j][high]][r][c] == -1)
					pq[i + dp[hsh[j][low - 1]][r][c]].push_back(S(r, c, j, high));
			}
			for (int j = high + 1;j <= k;j++) {
				if (dp[hsh[high + 1][j]][r][c] != -1 && dp[hsh[low][j]][r][c] == -1)
					pq[i + dp[hsh[high + 1][j]][r][c]].push_back(S(r, c, low, j));
			}
		}
		pq[i].clear();
	}
	if (ans == oo) ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:46:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &k, &m, &n);
                             ^
robots.cpp:48:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", grid[i]);
                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 77560 KB Output is correct
2 Correct 63 ms 77560 KB Output is correct
3 Correct 59 ms 77608 KB Output is correct
4 Correct 66 ms 77716 KB Output is correct
5 Correct 69 ms 77824 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 77560 KB Output is correct
2 Correct 63 ms 77560 KB Output is correct
3 Correct 59 ms 77608 KB Output is correct
4 Correct 66 ms 77716 KB Output is correct
5 Correct 69 ms 77824 KB Output is correct
6 Correct 64 ms 77824 KB Output is correct
7 Correct 59 ms 77824 KB Output is correct
8 Correct 60 ms 77864 KB Output is correct
9 Correct 61 ms 77864 KB Output is correct
10 Correct 61 ms 77872 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 77560 KB Output is correct
2 Correct 63 ms 77560 KB Output is correct
3 Correct 59 ms 77608 KB Output is correct
4 Correct 66 ms 77716 KB Output is correct
5 Correct 69 ms 77824 KB Output is correct
6 Correct 64 ms 77824 KB Output is correct
7 Correct 59 ms 77824 KB Output is correct
8 Correct 60 ms 77864 KB Output is correct
9 Correct 61 ms 77864 KB Output is correct
10 Correct 61 ms 77872 KB Output is correct
11 Correct 397 ms 134400 KB Output is correct
12 Correct 66 ms 134400 KB Output is correct
13 Correct 65 ms 134400 KB Output is correct
14 Execution timed out 1540 ms 163840 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 77560 KB Output is correct
2 Correct 63 ms 77560 KB Output is correct
3 Correct 59 ms 77608 KB Output is correct
4 Correct 66 ms 77716 KB Output is correct
5 Correct 69 ms 77824 KB Output is correct
6 Correct 64 ms 77824 KB Output is correct
7 Correct 59 ms 77824 KB Output is correct
8 Correct 60 ms 77864 KB Output is correct
9 Correct 61 ms 77864 KB Output is correct
10 Correct 61 ms 77872 KB Output is correct
11 Correct 397 ms 134400 KB Output is correct
12 Correct 66 ms 134400 KB Output is correct
13 Correct 65 ms 134400 KB Output is correct
14 Execution timed out 1540 ms 163840 KB Time limit exceeded
15 Halted 0 ms 0 KB -