oj.uz

Submission #241412

# Submission time Handle Problem Language Result Execution time Memory
241412 2020-06-24T07:29:11 Z VEGAnn Jetpack (COCI16_jetpack) C++14
80 / 80
 34 ms 10488 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 10;
const int M = 100100;
vector<i2> vc;
int n = 10, m;
char c[N][M];
bool can[N][M];
i2 pr[N][M];

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> c[n - 1 - i][j];

    can[0][0] = 1;

    for (int j = 0; j < m - 1; j++)
    for (int i = 0; i < n; i++){
        if (!can[i][j]) continue;

        if (i == 0){
            if (c[i][j + 1] != 'X') {
                can[i][j + 1] = 1;
                pr[i][j + 1] = {i, j};
            }

            if (c[i + 1][j + 1] != 'X') {
                can[i + 1][j + 1] = 1;
                pr[i + 1][j + 1] = {i, j};
            }
        } else if (i == n - 1){
            if (c[i][j + 1] != 'X') {
                can[i][j + 1] = 1;
                pr[i][j + 1] = {i, j};
            }

            if (c[i - 1][j + 1] != 'X') {
                can[i - 1][j + 1] = 1;
                pr[i - 1][j + 1] = {i, j};
            }
        } else {
            if (c[i - 1][j + 1] != 'X') {
                can[i - 1][j + 1] = 1;
                pr[i - 1][j + 1] = {i, j};
            }

            if (c[i + 1][j + 1] != 'X') {
                can[i + 1][j + 1] = 1;
                pr[i + 1][j + 1] = {i, j};
            }
        }
    }

    for (int i = 0; i < n; i++){
        if (!can[i][m - 1]) continue;

        int ci = i, cj = m - 1, len = 0;

        while (cj > 0){
            i2 nw = pr[ci][cj];

            if (ci == n - 1){
                len++;
            } else if (ci == 0){
                if (len > 0){
                    vc.PB({cj, len});
                    len = 0;
                }
            } else {
                if (nw[0] < ci)
                    len++;
                else {
                    if (len > 0){
                        vc.PB({cj, len});
                        len = 0;
                    }
                }
            }

            ci = nw[0];
            cj = nw[1];
        }

        if (len > 0)
            vc.PB({0, len});

        break;
    }

    cout << sz(vc) << '\n';

    reverse(all(vc));

    for (i2 cr : vc)
        cout << cr[0] << " " << cr[1] << '\n';

    return 0;
}

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 6 ms 512 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 11 ms 2432 KB Output is correct
8 Correct 18 ms 5248 KB Output is correct
9 Correct 24 ms 7712 KB Output is correct
10 Correct 34 ms 10488 KB Output is correct