oj.uz

Submission #43311

# Submission time Handle Problem Language Result Execution time Memory
43311 2018-03-13T12:32:00 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[50][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 54 ms 67320 KB Output is correct
2 Correct 53 ms 67324 KB Output is correct
3 Correct 52 ms 67496 KB Output is correct
4 Correct 52 ms 67496 KB Output is correct
5 Correct 54 ms 67496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 67320 KB Output is correct
2 Correct 53 ms 67324 KB Output is correct
3 Correct 52 ms 67496 KB Output is correct
4 Correct 52 ms 67496 KB Output is correct
5 Correct 54 ms 67496 KB Output is correct
6 Correct 52 ms 67576 KB Output is correct
7 Correct 62 ms 67580 KB Output is correct
8 Correct 55 ms 67604 KB Output is correct
9 Correct 54 ms 67632 KB Output is correct
10 Correct 53 ms 67636 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 67320 KB Output is correct
2 Correct 53 ms 67324 KB Output is correct
3 Correct 52 ms 67496 KB Output is correct
4 Correct 52 ms 67496 KB Output is correct
5 Correct 54 ms 67496 KB Output is correct
6 Correct 52 ms 67576 KB Output is correct
7 Correct 62 ms 67580 KB Output is correct
8 Correct 55 ms 67604 KB Output is correct
9 Correct 54 ms 67632 KB Output is correct
10 Correct 53 ms 67636 KB Output is correct
11 Correct 424 ms 124300 KB Output is correct
12 Correct 60 ms 124300 KB Output is correct
13 Correct 61 ms 124300 KB Output is correct
14 Execution timed out 1537 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 54 ms 67320 KB Output is correct
2 Correct 53 ms 67324 KB Output is correct
3 Correct 52 ms 67496 KB Output is correct
4 Correct 52 ms 67496 KB Output is correct
5 Correct 54 ms 67496 KB Output is correct
6 Correct 52 ms 67576 KB Output is correct
7 Correct 62 ms 67580 KB Output is correct
8 Correct 55 ms 67604 KB Output is correct
9 Correct 54 ms 67632 KB Output is correct
10 Correct 53 ms 67636 KB Output is correct
11 Correct 424 ms 124300 KB Output is correct
12 Correct 60 ms 124300 KB Output is correct
13 Correct 61 ms 124300 KB Output is correct
14 Execution timed out 1537 ms 163840 KB Time limit exceeded
15 Halted 0 ms 0 KB -