oj.uz

Submission #381963

# Submission time Handle Problem Language Result Execution time Memory
381963 2021-03-26T07:47:24 Z kartel Patkice II (COCI21_patkice2) C++14
110 / 110
 1259 ms 100388 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 2e3 + 50;

int steps[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
set <pair <int, pii> > q;
int n, m, sx, sy, ex, ey;
int nm[300];
int d[N][N];
char c[N][N], ans[N][N];
pii pr[N][N];

void go(int x, int y, int cnt, int i) {
    if (i == 4) {
        return;
    }

    int cx = x + steps[i][0];
    int cy = y + steps[i][1];

    if (cx < 1 || cy < 1 || cx > n || cy > m || d[cx][cy] <= cnt) {
        return;
    }

    d[cx][cy] = cnt;

    q.insert({cnt, {cx, cy}});
    pr[cx][cy] = {x, y};
}

void change(int x, int y, int cnt) {
    for (int i = 0; i < 4; i++) {
        go(x, y, cnt + 1, i);
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            d[i][j] = 1e9;
        }
    }

    d[sx][sy] = 0;

    for (int i = 0; i < 4; i++) {
        int cx = sx + steps[i][0];
        int cy = sy + steps[i][1];

        if (cx < 1 || cy < 1 || cx > n || cy > m || d[cx][cy] <= 0) {
            continue;
        }

        d[cx][cy] = 0;

        q.insert({0, {cx, cy}});
        pr[cx][cy] = {sx, sy};
    }

    while (sz(q)) {
        int x = (*q.begin()).S.F;
        int y = (*q.begin()).S.S;
        int cnt = (*q.begin()).F;

        q.erase(q.begin());
        if (x == ex && y == ey) {
            break;
        }

        go(x, y, cnt, nm[c[x][y]]);
        change(x, y, cnt);
    }
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n >> m;

    char cc[4];
    nm['<'] = 0; nm['>'] = 1; nm['v'] = 2; nm['^'] = 3; nm['.'] = 4;
    cc[0] = '<'; cc[1] = '>'; cc[2] = 'v'; cc[3] = '^';

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j]; ans[i][j] = c[i][j];

            if (c[i][j] == 'o') {
                sx = i;
                sy = j;
            }

            if (c[i][j] == 'x') {
                ex = i;
                ey = j;
            }
        }
    }

    solve();

    cout << d[ex][ey] << el;
    while (1) {
        int x = pr[ex][ey].F;
        int y = pr[ex][ey].S;

        if (x == sx && y == sy) {
            break;
        }

        for (int i = 0; i < 4; i++) {
            int cx = x + steps[i][0];
            int cy = y + steps[i][1];

            if (cx < 1 || cy < 1 || cx > n || cy > m) {
                continue;
            }

            if (cx == ex && cy == ey) {
                ans[x][y] = cc[i];
            }
        }
        ex = x;
        ey = y;
    }

    for (int i = 1; i <= n; i++, cout << el) {
        for (int j = 1; j <= m; j++) {
            cout << ans[i][j];
        }
    }
}


/*

7
4 6 7 2 3 1 5
*/

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:99:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   99 |         go(x, y, cnt, nm[c[x][y]]);
      |                          ~~~~~~^

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 1 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 1 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 93 ms 12240 KB Output is correct
7 Correct 122 ms 24812 KB Output is correct
8 Correct 331 ms 26220 KB Output is correct
9 Correct 573 ms 59756 KB Output is correct
10 Correct 824 ms 51180 KB Output is correct
11 Correct 1259 ms 100388 KB Output is correct