oj.uz

Submission #394545

# Submission time Handle Problem Language Result Execution time Memory
394545 2021-04-26T20:16:50 Z TimothyW553 Jetpack (COCI16_jetpack) C++14
80 / 80
 85 ms 10956 KB 
#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

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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9932 KB Output is correct
2 Correct 6 ms 9932 KB Output is correct
3 Correct 6 ms 9932 KB Output is correct
4 Correct 6 ms 9976 KB Output is correct
5 Correct 9 ms 9932 KB Output is correct
6 Correct 11 ms 9932 KB Output is correct
7 Correct 23 ms 9932 KB Output is correct
8 Correct 48 ms 10060 KB Output is correct
9 Correct 68 ms 10488 KB Output is correct
10 Correct 85 ms 10956 KB Output is correct