Submission #1278573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278573		wedonttalkanymore	Robots (APIO13_robots)	C++20	60 / 100	1133 ms	229376 KiB

robots

// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
/*
    Wake up, I'm wake up
    Thu sang roi, em thay khong?
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<int, int>
#define fi first
#define se second

const int N = 5e2 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 19;

int n, w, h;
char a[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
pii pre[N][N][4];
int preid[N][N][4];
vector<vector<vector<int>>> dp;
vector<pii> stops;

pii dfs(int x, int y, int k) {
    if (pre[x][y][k].se == -1) {
        int nx = 0, ny = 0, nk = k;
        pre[x][y][k].se = 0;
        if (a[x][y] == 'A') {
            nk = (k + 3) % 4;
        }
        else if (a[x][y] == 'C') {
            nk = (k + 1) % 4;
        }
        nx = x + dx[nk];
        ny = y + dy[nk];
        if (nx < 1 || ny < 1 || nx > h || ny > w || a[nx][ny] == 'x') {
            pre[x][y][k] = make_pair(x, y);
        }
        else pre[x][y][k] = dfs(nx, ny, nk);
    }
    return pre[x][y][k];
}

void precompute() {
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int k = 0; k < 4; k++) {
                pre[i][j][k] = make_pair(-1, -1);
            }
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int k = 0; k < 4; k++) {
                dfs(i, j, k);
            }
        }
    }
}

struct item {
    int si, L, R, val;
    bool operator <(const item &other) const {
        return val > other.val;
    }
};

int key(int x, int y) {
    return (x << 32) | y;
}

void dijkstra(int len) {
    int sz = (int)stops.size();
    for (int s = 0; s < sz; s++) {
        for (int R = len; R <= n; R++) {
            int L = R - len + 1;
            dp[s][L][R] = inf;
        }
    }
    priority_queue<item> q;
    if (len == 1) {
        for (int si = 0; si < sz; si++) {
            auto &p = stops[si];
            int i = p.fi, j = p.se;
            for (int R = 1; R <= n; R++) {
                if (a[i][j] - '0' == R) {
                    dp[si][R][R] = 0;
                    q.push({si, R, R, 0});
                }
            }
        }
    }
    else {
        for (int si = 0; si < sz; si++) {
            for (int R = len; R <= n; R++) {
                int L = R - len + 1;
                int val = inf;
                for (int k = L; k < R; k++) {
                    val = min(val, dp[si][L][k] + dp[si][k + 1][R]);
                }
                if (val < inf) {
                    dp[si][L][R] = val;
                    q.push({si, L, R, val});
                }
            }
        }
    }
    while (!q.empty()) {
        auto [si, L, R, val] = q.top();
        q.pop();
        if (dp[si][L][R] != val) continue;
        int x = stops[si].fi, y = stops[si].se;
        for (int i = 0; i < 4; i++) {
            int pid = preid[x][y][i];
            if (pid < 0) continue;
            if (dp[pid][L][R] > dp[si][L][R] + 1) {
                dp[pid][L][R] = dp[si][L][R] + 1;
                q.push({pid, L, R, dp[pid][L][R]});
            }
        }
    }
}

void solve() {
    for (int len = 1; len <= n; len++) {
        dijkstra(len);
    }
    int ans = inf;
    int sz = (int)stops.size();
    for (int si = 0; si < sz; si++) {
        ans = min(ans, dp[si][1][n]);
    }
    cout << (ans >= inf ? -1 : ans);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> w >> h;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
        }
    }
    precompute();
    {
        map<int, int> idx;
        for (int x = 1; x <= h; ++x) {
            for (int y = 1; y <= w; ++y) {
                for (int d = 0; d < 4; ++d) {
                    auto p = pre[x][y][d];
                    if (p.fi >= 1) {
                        int k = key(p.fi,p.se);
                        if (!idx.count(k)) {
                            idx[k] = stops.size();
                            stops.push_back(p);
                        }
                    }
                }
            }
        }
        for (int x = 1; x <= h; ++x) {
            for (int y = 1; y <= w; ++y) {
                if (a[x][y] >= '1' && a[x][y] <= '9') {
                    int k = key(x, y);
                    if (!idx.count(k)) {
                        idx[k] = stops.size();
                        stops.push_back({x,y});
                    }
                }
            }
        }
        for (int x = 1; x <= h; ++x) {
            for (int y = 1; y <= w; ++y) {
                for (int d = 0; d < 4; ++d) {
                    auto p = pre[x][y][d];
                    if (p.fi >= 1) preid[x][y][d] = idx[key(p.fi,p.se)];
                    else preid[x][y][d] = -1;
                }
            }
        }
    }
    int sz = (int)stops.size();
    dp.assign(sz, vector<vector<int>>(n + 2, vector<int>(n + 2, inf)));
    solve();
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
robots.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40