Submission #604076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
604076	2022-07-24T17:10:23 Z	nguyen31hoang08minh2003	Patkice II (COCI21_patkice2)	C++14	110 / 110	193 ms	43908 KB

Main

/*
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\
\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/
/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\
\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/
/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\
\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\/|\---\/---/|\
\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/\||\--/\--/||/
/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\/|||\//\\/|||\
\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/\|||/\\//\|||/
/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\/||/--\/--\||\
\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/\|/---/\---\|/
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define maxR 2005
#define maxC 2005
const int inf = 0x3f3f3f3f;
const short directions[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
const string ways = "^<>v";

bool seen[maxR][maxC];
short trace[maxR][maxC];
int r, s, d[maxR][maxC];
string sea[maxC];
deque<ii> dq;

void Input() {
    memset(d, inf, sizeof(d));
    cin >> r >> s;
    fore(x, 0, r) {
        cin >> sea[x];
        fore(y, 0, s)
            if (sea[x][y] == 'o') {
                int u, v;
                d[x][y] = 0;
                dq.emplace_back(x, y);
                fore(t, 0, 4) {
                    u = directions[t][0] + x;
                    v = directions[t][1] + y;
                    if (u < 0 || v < 0 || u >= r || v >= s)
                        continue;
                    if (mini(d[u][v], d[x][y])) {
                        dq.emplace_back(u, v);
                        trace[u][v] = t;
                    }
                }
            }
    }
}

void Solve() {
    for (int x, y, u, v; !dq.empty();) {
        x = dq.front().fi;
        y = dq.front().se;
        dq.pop_front();
        if (seen[x][y])
            continue;
        if (sea[x][y] == 'x') {
            cout << d[x][y] << '\n';
            while (sea[x][y] != 'o') {
                const int &t = trace[x][y];
                u = x - directions[t][0];
                v = y - directions[t][1];
                if (sea[u][v] != 'o')
                    sea[u][v] = ways[t];
                x = u;
                y = v;
            }
            fore(x, 0, r)
                cout << sea[x] << '\n';
            return;
        }
        seen[x][y] = true;
        fore(t, 0, 4) {
            u = directions[t][0] + x;
            v = directions[t][1] + y;
            if (u < 0 || v < 0 || u >= r || v >= s)
                continue;
            if (ways[t] == sea[x][y]) {
                if (mini(d[u][v], d[x][y])) {
                    dq.emplace_front(u, v);
                    trace[u][v] = t;
                }
            } else if (sea[x][y] != 'o') {
                if (mini(d[u][v], d[x][y] + 1)) {
                    dq.emplace_back(u, v);
                    trace[u][v] = t;
                }
            }
        }
    }
//    fore(x, 0, r) {
//        fore(y, 0, s)
//            cerr << d[x][y] << ' ';
//        cerr << '\n';
//    }
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    Input();
    Solve();
    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	16084 KB	Output is correct
2	Correct	8 ms	16084 KB	Output is correct
3	Correct	8 ms	16096 KB	Output is correct
4	Correct	13 ms	16124 KB	Output is correct
5	Correct	7 ms	16124 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	16084 KB	Output is correct
2	Correct	8 ms	16084 KB	Output is correct
3	Correct	8 ms	16096 KB	Output is correct
4	Correct	13 ms	16124 KB	Output is correct
5	Correct	7 ms	16124 KB	Output is correct
6	Correct	26 ms	20544 KB	Output is correct
7	Correct	27 ms	24004 KB	Output is correct
8	Correct	68 ms	25932 KB	Output is correct
9	Correct	107 ms	33680 KB	Output is correct
10	Correct	168 ms	35880 KB	Output is correct
11	Correct	193 ms	43908 KB	Output is correct