oj.uz

Submission #241303

# Submission time Handle Problem Language Result Execution time Memory
241303 2020-06-23T19:01:09 Z dolphingarlic Robots (APIO13_robots) C++14
60 / 100
 1500 ms 91028 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int INF = 1061109567;

int n, h, w;
char g[500][500];
pair<int, int> end_pos[500][500][4];
int dp[500][500][9][9];

bool inside(int x, int y) {
    return (x >= 0 && y >= 0 && x < h && y < w && g[x][y] != 'x');
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> w >> h;
    memset(dp, 0x3f, sizeof(dp));

    FOR(i, 0, h) FOR(j, 0, w) {
        cin >> g[i][j];
        if (g[i][j] - '0' > 0 && g[i][j] - '0' < 10) {
            dp[i][j][g[i][j] - '1'][g[i][j] - '1'] = 0;
        }
        FOR(k, 0, 4) end_pos[i][j][k] = {-1, -1};
    }

    // Determine final positions from each push
    FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
        FOR(k, 0, 4) {
            pair<int, int> pos = {i, j};
            int d = (k + (g[i][j] == 'A') * 3 + (g[i][j] == 'C')) % 4;  // NESW

            while (true) {
                if (d == 0) {
                    if (inside(pos.first - 1, pos.second)) pos.first--;
                    else break;
                } else if (d == 1) {
                    if (inside(pos.first, pos.second + 1)) pos.second++;
                    else break;
                } else if (d == 2) {
                    if (inside(pos.first + 1, pos.second)) pos.first++;
                    else break;
                } else {
                    if (inside(pos.first, pos.second - 1)) pos.second--;
                    else break;
                }

                if (~end_pos[pos.first][pos.second][d].first) {
                    pos = end_pos[pos.first][pos.second][d];
                    break;
                }

                if (g[pos.first][pos.second] == 'A') d = (d + 3) % 4;
                if (g[pos.first][pos.second] == 'C') d = (d + 1) % 4;
            }

            end_pos[i][j][k] = pos;
        }
    }

    // Find the minimum no. of pushes to get robot k-l to block (i, j)
    FOR(rng, 0, n) {
        FOR(k, 0, n - rng) {
            int l = k + rng;
            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
                FOR(d, k, l) {
                    dp[i][j][k][l] =
                        min(dp[i][j][k][l],
                            dp[i][j][k][d] + dp[i][j][d + 1][l]);
                }
            }
        }

        FOR(k, 0, n - rng) {
            int l = k + rng;
            priority_queue<pair<int, pair<int, int>>> pq;
            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
                if (dp[i][j][k][l] != INF) {
                    pq.push({-dp[i][j][k][l], {i, j}});
                }
            }
            while (pq.size()) {
                int x, y;
                tie(x, y) = pq.top().second;
                pq.pop();
                FOR(dir, 0, 4) {
                    int nx, ny;
                    tie(nx, ny) = end_pos[x][y][dir];
                    if (dp[nx][ny][k][l] > dp[x][y][k][l] + 1) {
                        dp[nx][ny][k][l] = dp[x][y][k][l] + 1;
                        pq.push({-dp[nx][ny][k][l], {nx, ny}});
                    }
                }
            }
        }
    }

    int ans = INT_MAX;
    FOR(i, 0, h) FOR(j, 0, w) ans = min(ans, dp[i][j][0][n - 1]);
    cout << (ans == INF ? -1 : ans);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 79608 KB Output is correct
2 Correct 45 ms 79608 KB Output is correct
3 Correct 46 ms 79608 KB Output is correct
4 Correct 49 ms 79608 KB Output is correct
5 Correct 49 ms 79652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 79608 KB Output is correct
2 Correct 45 ms 79608 KB Output is correct
3 Correct 46 ms 79608 KB Output is correct
4 Correct 49 ms 79608 KB Output is correct
5 Correct 49 ms 79652 KB Output is correct
6 Correct 48 ms 79608 KB Output is correct
7 Correct 45 ms 79608 KB Output is correct
8 Correct 46 ms 79608 KB Output is correct
9 Correct 49 ms 79608 KB Output is correct
10 Correct 45 ms 79608 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 79608 KB Output is correct
2 Correct 45 ms 79608 KB Output is correct
3 Correct 46 ms 79608 KB Output is correct
4 Correct 49 ms 79608 KB Output is correct
5 Correct 49 ms 79652 KB Output is correct
6 Correct 48 ms 79608 KB Output is correct
7 Correct 45 ms 79608 KB Output is correct
8 Correct 46 ms 79608 KB Output is correct
9 Correct 49 ms 79608 KB Output is correct
10 Correct 45 ms 79608 KB Output is correct
11 Correct 257 ms 84376 KB Output is correct
12 Correct 57 ms 83628 KB Output is correct
13 Correct 122 ms 83832 KB Output is correct
14 Correct 850 ms 85260 KB Output is correct
15 Correct 184 ms 84112 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 79608 KB Output is correct
2 Correct 45 ms 79608 KB Output is correct
3 Correct 46 ms 79608 KB Output is correct
4 Correct 49 ms 79608 KB Output is correct
5 Correct 49 ms 79652 KB Output is correct
6 Correct 48 ms 79608 KB Output is correct
7 Correct 45 ms 79608 KB Output is correct
8 Correct 46 ms 79608 KB Output is correct
9 Correct 49 ms 79608 KB Output is correct
10 Correct 45 ms 79608 KB Output is correct
11 Correct 257 ms 84376 KB Output is correct
12 Correct 57 ms 83628 KB Output is correct
13 Correct 122 ms 83832 KB Output is correct
14 Correct 850 ms 85260 KB Output is correct
15 Correct 184 ms 84112 KB Output is correct
16 Correct 568 ms 87928 KB Output is correct
17 Execution timed out 1597 ms 91028 KB Time limit exceeded
18 Halted 0 ms 0 KB -