Submission #381976

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381976	2021-03-26T08:18:53 Z	NONAME	Patkice II (COCI21_patkice2)	C++17	110 / 110	1420 ms	91372 KB

Main

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, const T b) {a = min(a, b); return (a == b);}
template <typename T> inline bool chmax(T& a, const T b) {a = max(a, b); return (a == b);}

const int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int man = (int)(2e3 + 10);

int n, m, sx, sy, ex, ey;
int a[man][man], d[man][man];
array <int, 3> pr[man][man];

inline void cls() {}

void solve() {
    cls();

    string st = ".v>^<ox";

    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            d[i][j] = 1e9;
            pr[i][j] = {-1, -1, -1};
            char c;
            cin >> c;
            if (c == '.') {
                a[i][j] = 0;
            }
            if (c == 'v') {
                a[i][j] = 1;
            }
            if (c == '>') {
                a[i][j] = 2;
            }
            if (c == '^') {
                a[i][j] = 3;
            }
            if (c == '<') {
                a[i][j] = 4;
            }
            if (c == 'o') {
                a[i][j] = 5;
                sx = i, sy = j;
            }
            if (c == 'x') {
                a[i][j] = 6;
                ex = i, ey = j;
            }
        }
    }

    priority_queue <array <int, 3> > q;
    q.push({0, sx, sy});
    d[sx][sy] = 0;
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        int c = -cur[0], x = cur[1], y = cur[2];
        if (a[x][y] == 6) {
            continue;
        }
        if (c != d[x][y]) {
            continue;
        }

        if ((x == sx) && (y == sy)) {
            for (int i = 0; i < 4; ++i) {
                int cx = x + steps[i][0];
                int cy = y + steps[i][1];
                if ((cx >= 0) && (cx < n) && (cy >= 0) && (cy < m)) {
                    d[cx][cy] = 0;
                    pr[cx][cy] = {x, y, i + 1};
                    q.push({0, cx, cy});
                }
            }
        } else {
            for (int i = 0; i < 4; ++i) {
                int cx = x + steps[i][0];
                int cy = y + steps[i][1];

                if ((cx >= 0) && (cx < n) && (cy >= 0) && (cy < m) && ((c + ((i + 1) != a[x][y])) < d[cx][cy])) {
                    d[cx][cy] = c + ((i + 1) != a[x][y]);
                    pr[cx][cy] = {x, y, i + 1};
                    q.push({-d[cx][cy], cx, cy});
                }
            }
        }
    }

    int x = ex, y = ey, tp = -1;
    while ((x != sx) || (y != sy)) {
        if (tp != -1) {
            a[x][y] = tp;
        }
        int ox = x, oy = y;
        x = pr[ox][oy][0];
        y = pr[ox][oy][1];
        tp = pr[ox][oy][2];
    }

    cout << d[ex][ey] << "\n";
    for (int i = 0; i < n; ++i, cout << "\n") {
        for (int j = 0; j < m; ++j) {
            cout << st[a[i][j]];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    #ifdef _LOCAL
        system("color a");
        freopen("in.txt", "r", stdin);
        cin >> t;
    #endif

    for (int i = 1; i <= t; ++i) {
        cerr << "Case #" << i << ": \n";
        solve();
        cerr << "\n";
    }

    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	157 ms	17992 KB	Output is correct
7	Correct	192 ms	23592 KB	Output is correct
8	Correct	392 ms	38380 KB	Output is correct
9	Correct	836 ms	60252 KB	Output is correct
10	Correct	1026 ms	72472 KB	Output is correct
11	Correct	1420 ms	91372 KB	Output is correct