oj.uz

Submission #381959

# Submission time Handle Problem Language Result Execution time Memory
381959 2021-03-26T07:43:31 Z kartel Patkice II (COCI21_patkice2) C++14
55 / 110
 1221 ms 64372 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];

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}});
}

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}});
    }

    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;

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> 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;

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


/*

7
4 6 7 2 3 1 5
*/

Compilation message

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

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Partially correct
2 Partially correct 1 ms 364 KB Partially correct
3 Partially correct 1 ms 492 KB Partially correct
4 Partially correct 1 ms 492 KB Partially correct
5 Partially correct 1 ms 364 KB Partially correct

Subtask #2
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 364 KB Partially correct
2 Partially correct 1 ms 364 KB Partially correct
3 Partially correct 1 ms 492 KB Partially correct
4 Partially correct 1 ms 492 KB Partially correct
5 Partially correct 1 ms 364 KB Partially correct
6 Partially correct 99 ms 6636 KB Partially correct
7 Partially correct 125 ms 15084 KB Partially correct
8 Partially correct 348 ms 12780 KB Partially correct
9 Partially correct 585 ms 35324 KB Partially correct
10 Partially correct 752 ms 21444 KB Partially correct
11 Partially correct 1221 ms 64372 KB Partially correct