Submission #248403

#	Time	Username	Problem	Language	Result	Execution time	Memory
248403		receed	Robots (APIO13_robots)	C++14	100 / 100	556 ms	51724 KiB

robots

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 501, INF = 1e9;
char a[N][N];
int to[N * N][4], tr[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}, used[N * N];
int d[9][9][N * N];
int n, w, h;

int getn(int x, int y) {
    return x * w + y;
}

int go(int x, int y, int dr) {
    if (x < 0 || x >= h || y < 0 || y >= w || a[x][y] == 'x')
        return getn(x - tr[dr][0], y - tr[dr][1]);
    int num = getn(x, y);
    if (to[num][dr] != -1)
        return to[num][dr];
    to[num][dr] = -2;
    int nd = dr;
    if (a[x][y] == 'A')
        nd = (dr + 1) % 4;
    else if (a[x][y] == 'C')
        nd = (dr + 3) % 4;
    x += tr[nd][0];
    y += tr[nd][1];
    to[num][dr] = go(x, y, nd);
    return to[num][dr];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> w >> h;
    rep(i, h)
        cin >> a[i];
    rep(i, w * h)
        rep(j, 4)
            to[i][j] = -1;
    rep(i, h)
        rep(j, w)
            if (a[i][j] != 'x')
                rep(k, 4)
                    go(i, j, k);
    int v;
    for (int l = n - 1; l >= 0; l--)
        for (int r = l; r < n; r++) {
            vector<pair<int, int>> li;
            rep(i, h * w) {
                used[i] = 0;
                d[l][r][i] = INF;
                if (l == r && a[i / w][i % w] == '1' + l)
                    d[l][r][i] = 0;
                for (int j = l; j < r; j++)
                    d[l][r][i] = min(d[l][r][i], d[l][j][i] + d[j + 1][r][i]);
                if (d[l][r][i] < INF)
                    li.push_back({d[l][r][i], i});
            }
            queue<int> q;
            sort(rall(li));
            while (!q.empty() || !li.empty()) {
                if (li.empty() || !q.empty() && d[l][r][q.front()] < li.back().first) {
                    v = q.front();
                    q.pop();
                }
                else {
                    v = li.back().second;
                    li.pop_back();
                }
                if (used[v])
                    continue;
                used[v] = 1;
                rep(i, 4)
                    if (to[v][i] >= 0 && d[l][r][to[v][i]] > d[l][r][v] + 1) {
                        d[l][r][to[v][i]] = d[l][r][v] + 1;
                        q.push(to[v][i]);
                    }
            }
        }
    int ans = INF;
    rep(i, h * w)
        ans = min(ans, d[0][n - 1][i]);
    if (ans == INF)
        ans = -1;
    cout << ans;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:86:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 if (li.empty() || !q.empty() && d[l][r][q.front()] < li.back().first) {
                                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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