Submission #1278567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278567		wedonttalkanymore	Robots (APIO13_robots)	C++20	60 / 100	1604 ms	156180 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}; // tren, phai, duoi, trai
int dy[] = {0, 1, 0, -1};
pii pre[N][N][4];
int preid[N][N][4];
int dp[N][N][10][10];
vector<pii> stops;

pii dfs(int x, int y, int k) {
    // cout << x << ' ' << y << ' ' << k << '\n';
    // cout << pre[x][y][k].se << '\n';
    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;
        }
        // if (x == 2 && y == 2 && k == 2) cout << "at: " << k << ' ' << nk << '\n';
        nx = x + dx[nk];
        ny = y + dy[nk];
        // cout << "now: " << nx << ' ' << ny << ' ' << nk << '\n';
        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);
            }
        }
    }
    // dfs(1, 1, 2);
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int k = 0; k < 4; k++) {
                // cout << i << ' ' << j << ' ' << k << '\n';
                // cout << "now: " << pre[i][j][k].fi << ' ' << pre[i][j][k].se << '\n';
            }
        }
    }
}

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

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

void dijkstra(int len) {
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            for (int R = len; R <= n; R++) {
                int L = R - len + 1;
                dp[i][j][L][R] = inf;
            }
        }
    }
    priority_queue <item> q;
    if (len == 1) {
        for (auto &p : stops) {
            int i = p.fi, j = p.se;
            for (int R = 1; R <= n; R++) {
                if (a[i][j] - '0' == R) {
                    dp[i][j][R][R] = 0;
                    q.push({i, j, R, R, 0});
                }
            }
        }
    }
    else {
        for (auto &p : stops) {
            int i = p.fi, j = p.se;
            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[i][j][L][k] + dp[i][j][k + 1][R]);
                }
                if (val < inf) {
                    dp[i][j][L][R] = val;
                    q.push({i, j, L, R, val});
                }
            }
        }
    }
    while(q.size()) {
        auto [x, y, L, R, val] = q.top();
        q.pop();
        if (dp[x][y][L][R] != val) continue;
        for (int i = 0; i < 4; i++) {
            int nx = pre[x][y][i].fi, ny = pre[x][y][i].se;
            if (nx < 1) continue;
            if (dp[nx][ny][L][R] > dp[x][y][L][R] + 1) {
                dp[nx][ny][L][R] = dp[x][y][L][R] + 1;
                q.push({nx, ny, L, R, dp[nx][ny][L][R]});
            }
        }
    }
}

void solve() {
    for (int len = 1; len <= n; len++) {
        dijkstra(len);
    }
    int ans = inf;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            // cout << i << ' ' << j << ' ' << dp[i][j][1][n] << '\n';
            ans = min(ans, dp[i][j][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 <ll, 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) {
                        ll 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') {
                    ll 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;
                }
            }
        }
    }
    solve();
    return 0;
}

Compilation message (stderr)

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

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