oj.uz

Submission #241879

# Submission time Handle Problem Language Result Execution time Memory
241879 2020-06-26T08:23:17 Z NONAME Jetpack (COCI16_jetpack) C++14
16 / 80
 35 ms 10744 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

int n, m, d[10][int(1e5) + 10], pr[10][int(1e5) + 10];
char c[10][int(1e5) + 10];
queue <pair <int, int> > q;

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

    #ifdef _LOCAL
        freopen("in", "r", stdin);
        freopen("out", "w", stdout);
    #endif // _LOCAL

    cin >> m;
    n = 10;
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        cin >> c[i][j];

    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        d[i][j] = 2 * m, pr[i][j] = -1;

    q.push(make_pair(n - 1, 0));
    d[n - 1][0] = 0;

    while (!q.empty()) {
        auto o = q.front();
        q.pop();

        if (o.second == m - 1)
            continue;

        if (o.first == n - 1 || o.first == 0) {
            if (c[o.first][o.second + 1] != 'X' && d[o.first][o.second + 1] > d[o.first][o.second] + 1) {
                q.push(make_pair(o.first, o.second + 1));
                d[o.first][o.second + 1] = d[o.first][o.second] + 1;
                pr[o.first][o.second + 1] = o.first;
            }
        }

        if (o.first != 0) {
            if (c[o.first - 1][o.second + 1] != 'X' && d[o.first - 1][o.second + 1] > d[o.first][o.second] + 1) {
                q.push(make_pair(o.first - 1, o.second + 1));
                d[o.first - 1][o.second + 1] = d[o.first][o.second] + 1;
                pr[o.first - 1][o.second + 1] = o.first;
            }
        }

        if (o.first != n - 1) {
            if (c[o.first + 1][o.second + 1] != 'X' && d[o.first + 1][o.second + 1] > d[o.first][o.second] + 1) {
                q.push(make_pair(o.first + 1, o.second + 1));
                d[o.first + 1][o.second + 1] = d[o.first][o.second] + 1;
                pr[o.first + 1][o.second + 1] = o.first;
            }
        }
    }

    int p = -1;

    for (int i = 0; i < n; ++i)
        if (pr[i][m - 1] != -1 && (p == -1 || d[i][m - 1] < d[p][m - 1]))
            p = i;

    vector <pair <int, int> > res;
    res.clear();
    int lst = p, t = m - 2;
    int cr = pr[p][m - 1];

    while (cr != -1) {
        if (cr - 1 == lst)
            res.push_back(make_pair(t, 1));

        --t;
        lst = cr;
        cr = pr[cr][t + 1];
    }

    sort(res.begin(), res.end());
    cout << int(res.size()) << "\n";
    for (auto i : res)
        cout << i.first << " " << i.second << "\n";
}

Subtask #1
16.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Incorrect 5 ms 512 KB Crashed with an obstacle
4 Incorrect 5 ms 512 KB Crashed with an obstacle
5 Incorrect 6 ms 896 KB Crashed with an obstacle
6 Incorrect 7 ms 1152 KB Crashed with an obstacle
7 Incorrect 11 ms 2432 KB Crashed with an obstacle
8 Incorrect 20 ms 5376 KB Crashed with an obstacle
9 Incorrect 28 ms 7928 KB Crashed with an obstacle
10 Incorrect 35 ms 10744 KB Crashed with an obstacle