oj.uz

Submission #241623

# Submission time Handle Problem Language Result Execution time Memory
241623 2020-06-24T20:43:53 Z ffao Robots (APIO13_robots) C++14
30 / 100
 1500 ms 94064 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int dist[9][9][510][510];

string board[510];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

pii dest[510][510][4];
int n, w, h;

pii follow(int x, int y, int d) {
    pii &ret = dest[x][y][d];
    if (ret.first != -1) return ret;

    if (board[x][y] == 'A') d = (d+3)%4;
    else if (board[x][y] == 'C') d=(d+1)%4;

    int nx = x+dx[d], ny = y+dy[d];
    if (nx < 0 || nx >= h || ny < 0 || ny >= w) return ret = {x, y};
    if (board[nx][ny] == 'x') return ret = {x,y};
    return follow(nx,ny,d);
}

void expand(int fr, int to) {
    vector< pair<int, pair<int, int> > > alldist;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            alldist.push_back({dist[fr][to][i][j], {i,j}});
        }
    }

    sort(all(alldist));

    queue<pair<int,int>> q;
    int at = 0;

    while (at < alldist.size()) {
        int aat = at;
        while (at < alldist.size() && alldist[at].first == alldist[aat].first) {
            if (dist[fr][to][alldist[at].second.first][alldist[at].second.second] == alldist[at].first) {
                q.push(alldist[at].second);
            }
            at++;
        }
        
        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;

            while (at < alldist.size() && alldist[at].first == dist[fr][to][x][y] + 1) {
                if (dist[fr][to][alldist[at].second.first][alldist[at].second.second] == alldist[at].first) {
                    q.push(alldist[at].second);
                }
                at++;
            }

            for (int d = 0; d < 4; d++) {
                pii nxt = follow(x, y, d);
                if (dist[fr][to][nxt.first][nxt.second] > dist[fr][to][x][y] + 1) {
                    dist[fr][to][nxt.first][nxt.second] = dist[fr][to][x][y] + 1;
                    q.push(nxt);
                }
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) cin >> board[i];

    memset(dist,0x3f,sizeof(dist));
    memset(dest, -1, sizeof(dest));
    for (int oi = 0; oi < h; oi++) {
        for (int oj = 0; oj < w; oj++) {
            if ('1' <= board[oi][oj] && board[oi][oj] <= '9') {
                int idx = board[oi][oj] - '1';
                dist[idx][idx][oi][oj] = 0;

                expand(idx,idx);
            }
        }
    }

    for (int len = 2; len <= n; len++) {
        for (int f = 0; f+len <= n; f++) {
            for (int spl = f; spl+1 < f+len; spl++) {
                for (int x = 0; x < h; x++) {
                    for (int y = 0; y < w; y++) {
                        dist[f][f+len-1][x][y] = min(dist[f][f+len-1][x][y], dist[f][spl][x][y] + dist[spl+1][f+len-1][x][y]);
                    }
                }
            }

            expand(f, f+len-1);
        }
    }

    // for (int i = 0; i < 4; i++)
    //     cout << follow(3, 0, i).first << " " << follow(3, 0, i).second << endl;

    // for (int i = 0; i < h; i++) {
    //     for (int j = 0; j < w; j++) {
    //         if ( cout << (? dist[1][1][i][j] : -1) << " ";
    //     }
    //     cout << endl;
    // }

    int ans = 1000000000;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            ans = min(ans, dist[0][n-1][i][j]);
        }
    }

    cout << (ans == 1000000000 ? -1 : ans);
    return 0;
}

Compilation message

robots.cpp: In function 'void expand(int, int)':
robots.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (at < alldist.size()) {
            ~~~^~~~~~~~~~~~~~~~
robots.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (at < alldist.size() && alldist[at].first == alldist[aat].first) {
                ~~~^~~~~~~~~~~~~~~~
robots.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (at < alldist.size() && alldist[at].first == dist[fr][to][x][y] + 1) {
                    ~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 91000 KB Output is correct
2 Correct 48 ms 90912 KB Output is correct
3 Correct 49 ms 91000 KB Output is correct
4 Correct 49 ms 91000 KB Output is correct
5 Correct 52 ms 91000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 91000 KB Output is correct
2 Correct 48 ms 90912 KB Output is correct
3 Correct 49 ms 91000 KB Output is correct
4 Correct 49 ms 91000 KB Output is correct
5 Correct 52 ms 91000 KB Output is correct
6 Correct 50 ms 90916 KB Output is correct
7 Correct 48 ms 91004 KB Output is correct
8 Correct 52 ms 91000 KB Output is correct
9 Correct 51 ms 91128 KB Output is correct
10 Correct 48 ms 91000 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 91000 KB Output is correct
2 Correct 48 ms 90912 KB Output is correct
3 Correct 49 ms 91000 KB Output is correct
4 Correct 49 ms 91000 KB Output is correct
5 Correct 52 ms 91000 KB Output is correct
6 Correct 50 ms 90916 KB Output is correct
7 Correct 48 ms 91004 KB Output is correct
8 Correct 52 ms 91000 KB Output is correct
9 Correct 51 ms 91128 KB Output is correct
10 Correct 48 ms 91000 KB Output is correct
11 Correct 537 ms 94064 KB Output is correct
12 Correct 63 ms 92784 KB Output is correct
13 Execution timed out 1591 ms 94000 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 91000 KB Output is correct
2 Correct 48 ms 90912 KB Output is correct
3 Correct 49 ms 91000 KB Output is correct
4 Correct 49 ms 91000 KB Output is correct
5 Correct 52 ms 91000 KB Output is correct
6 Correct 50 ms 90916 KB Output is correct
7 Correct 48 ms 91004 KB Output is correct
8 Correct 52 ms 91000 KB Output is correct
9 Correct 51 ms 91128 KB Output is correct
10 Correct 48 ms 91000 KB Output is correct
11 Correct 537 ms 94064 KB Output is correct
12 Correct 63 ms 92784 KB Output is correct
13 Execution timed out 1591 ms 94000 KB Time limit exceeded
14 Halted 0 ms 0 KB -