Submission #1136379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136379		ALTAKEXE	Robots (APIO13_robots)	C++17	0 / 100	48 ms	111940 KiB

robots

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define INF INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
const int MOD = 1e9 + 7;
using namespace std;
template <class T, class U>
bool chmin(T &a, const U &b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n, w, h;
pair<int, int> mem[500][500][4];
char s[501][501];
vector<pair<int, int>> g[500][500];
int cost[10][10][500][500];
pair<int, int> dfs(int x, int y, int d)
{
    if (x < 0)
        return {x + 1, y};
    if (y < 0)
        return {x, y + 1};
    if (x >= h)
        return {x - 1, y};
    if (y >= w)
        return {x, y - 1};
    if (s[x][y] == 'x')
        return {x + dx[d ^ 2], y + dy[d ^ 2]};
    if (mem[x][y][d] != pair<int, int>{-1, -1})
        return mem[x][y][d];
    int d2 = d;
    if (s[x][y] == 'A')
    {
        d2 += 3;
        d2 &= 3;
    }
    else if (s[x][y] == 'C')
    {
        d2 += 1;
        d2 &= 3;
    }
    mem[x][y][d] = {-2, -2};
    return mem[x][y][d] = dfs(x + dx[d2], y + dy[d2], d2);
}
void bfs(int u, int v)
{
    auto c = cost[u][v];
    for (int k = u + 1; k < v; k++)
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                c[i][j] = min(c[i][j], cost[u][k][i][j] + cost[k][v][i][j]);
    queue<array<int, 3>> q;
    vector<array<int, 3>> q2;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (c[i][j] != INF)
                q2.push_back({c[i][j], i, j});
    sort(q2.begin(), q2.end(), greater<array<int, 3>>());
    while (q.size() || q2.size())
    {
        bool ok = 0;
        if (!q2.size())
            ok = 1;
        else if (q.size() && q.front()[0] < q2.back()[0])
            ok = 1;
        auto [une, x, y] = ok ? q.front() : q2.back();
        if (ok)
            q.pop();
        else
            q2.pop_back();
        for (auto [x2, y2] : g[x][y])
        {
            if (c[x2][y2] > une + 1)
            {
                c[x2][y2] = une + 1;
                q.push({c[x2][y2], x2, y2});
            }
        }
    }
}
int main()
{
    memset(mem, 255, sizeof(mem));
    memset(cost, 51, sizeof(cost));
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++)
        scanf("%s", s[i]);
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            for (int d = 0; d < 4; d++)
                dfs(i, j, d);
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            for (int d = 0; d < 4; d++)
                if (mem[i][j][d] != pair<int, int>{-2, -2} && mem[i][j][d] != pair<int, int>{i, j})
                    g[i][j].push_back(mem[i][j][d]);
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            if (isdigit(s[i][j]))
                cost[s[i][j] - '1'][s[i][j] - '0'][i][j] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n - i; j++)
            bfs(j, j + i);
    int ans = INF;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            ans = min(ans, cost[0][n][i][j]);
    cout << ((ans == INF) ? -1 : ans) << endl;
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%s", s[i]);
      |         ~~~~~^~~~~~~~~~~~

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