oj.uz

Submission #241880

# Submission time Handle Problem Language Result Execution time Memory
241880 2020-06-26T08:25:31 Z NONAME Jetpack (COCI16_jetpack) C++14
80 / 80
 31 ms 9472 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], cur = 0;

    while (cr != -1) {
        if (cr - 1 == lst || (cr == lst && cr == 0)) ++cur;
            else if (cur != 0) res.push_back(make_pair(t + 1, cur)), cur = 0;

        --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
80.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 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 11 ms 2176 KB Output is correct
8 Correct 19 ms 4736 KB Output is correct
9 Correct 26 ms 6912 KB Output is correct
10 Correct 31 ms 9472 KB Output is correct