Submission #241880

#	Time	Username	Problem	Language	Result	Execution time	Memory
241880		NONAME	Jetpack (COCI16_jetpack)	C++14	80 / 80	31 ms	9472 KiB

jetpack

#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 / 80