Submission #394545

#	Time	Username	Problem	Language	Result	Execution time	Memory
394545		TimothyW553	Jetpack (COCI16_jetpack)	C++14	80 / 80	85 ms	10956 KiB

jetpack

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

const int maxN = 1e5 + 5;

vector<vector<char>> adj(10, vector<char>(maxN));
vector<int> path;
vector<pair<int, int>> dirs = {{-1, 1}, {1, 1}, {0, 1}};
vector<vector<pair<int, int>>> par(10, vector<pair<int, int>>(maxN, {-1, -1}));

int n;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    scanf("%i", &n);
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < n; j++)  {
            cin >> adj[i][j];
        }
    }
    queue<pair<int, int>> q;
    q.push({9, 0});
    adj[9][0] = 'X';
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        int r0 = cur.first, c0 = cur.second;
        for(auto &dir : dirs) {
            if((r0 != 9 and r0 != 0) and dir.first == 0) {
                continue;
            }
            int r = r0 + dir.first, c = c0 + dir.second;
            if(r >= 0 and r < 10 and c >= 0 and c < n and adj[r][c] == '.') {
                q.push({r, c});
                adj[r][c] = '*';
                par[r][c] = {r0, c0};
            }
        }
    }
    pair<int, int> src;
    for(int i = 9; i >= 0; i--) {
        if(par[i][n-1].first != -1) {
            src = {i, n-1};
            break;
        }
    }
    pair<int, int> cur = src;
    while(cur.first != -1 and cur.second != -1) {
        if(par[cur.first][cur.second].first >= cur.first) {
            if(cur.first == par[cur.first][cur.second].first and cur.first == 9) {
                cur = par[cur.first][cur.second];
                continue;
            }
            path.push_back(cur.second);
            adj[cur.first][cur.second] = '*';
        }
        cur = par[cur.first][cur.second];
    }
    /*for(int i = 0; i < 10; i++) {
        for(int j = 0; j < n; j++) {
            cout << "{" << par[i][j].first << ", " << par[i][j].second << "} ";
        }
        cout << "\n";
    }
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < n; j++) {
            cout << adj[i][j];
        }
        cout << "\n";
    }*/
    reverse(begin(path), end(path));
    printf("%i\n", int(path.size()));
    for(int i = 0; i < int(path.size()); i++) {
        printf("%i %i\n", path[i]-1, 1);
    }
    return 0;
}

Compilation message (stderr)

jetpack.cpp: In function 'int main()':
jetpack.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     scanf("%i", &n);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 80 / 80