제출 #543772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543772		kusssso	Jetpack (COCI16_jetpack)	C++17	16 / 80	33 ms	15492 KiB

jetpack

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int inf = INT_MAX;
const int N = 1e5 + 5;

bool minimize (int &self, int x) {
    if (self > x) {
        self = x;
        return true;
    }
    return false;
}

int n;
char a[15][N];
int d[15][N];
pair<int, int> tr[15][N];
queue<pair<int, int>> q;

bool legit (int i, int j) {
    return (1 <= i && i <= 10 && 1 <= j && j <= n && a[i][j] != 'X');
}

void go (int x, int y, int i, int j) {
    if (legit(x, y) && minimize(d[x][y], d[i][j] + 1)) {
        tr[x][y] = make_pair(i, j);
        q.push({x, y});
    }
}

bool upward (pair<int, int> u, pair<int, int> v) {
    return (u.first - v.first == 1 && v.second - u.second == 1);
}

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

    cin >> n;
    for (int i = 1; i <= 10; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
    for (int i = 1; i <= 10; i++) for (int j = 1; j <= n; j++) d[i][j] = inf, tr[i][j] = make_pair(-1, -1);
    q.push({10, 1});
    tr[10][1] = make_pair(10, 1);
    d[10][1] = 0;
    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        go(i - 1, j + 1, i, j);
        go(i + 1, j + 1, i, j);
        if (i == 1 || i == 10) {
            go(i, j + 1, i, j);
        }
    }
    int best = inf;
    int r = -1, c = n;
    for (int i = 1; i <= 10; i++) {
        if (a[i][n] != 'X') {
            if (minimize(best, d[i][n])) {
                r = i;
            }
        }
    }
    vector<pair<int, int>> route;
    while (tr[r][c] != make_pair(r, c)) {
        route.push_back({r, c});
        pair<int, int> cur = tr[r][c];
        r = cur.first;
        c = cur.second;
    }
    route.push_back({10, 1});
    reverse(route.begin(), route.end());
//    cout << route.size() << '\n';
//    for (pair<int, int> u : route) {
//        cout << u.first << ' ' << u.second << '\n';
//    }
    vector<pair<int, int>> res;
    int start = -1;
    int duration = 0;
    for (int i = 1; i < (int) route.size(); i++) {
        if (upward(route[i - 1], route[i])) {
            if (!duration) start = i - 1;
            duration++;
        }
        else {
            if (start != -1) {
                res.push_back({start, duration});
            }
            start = -1;
            duration = 0;
        }
    }
    if (start != -1) {
        res.push_back({start, duration});
    }
    cout << res.size() << '\n';
    for (auto [x, y] : res) {
        cout << x << ' ' << y << '\n';
    }

    return 0;
}

• Subtask 1: 16 / 80