Submission #241412

#	Time	Username	Problem	Language	Result	Execution time	Memory
241412		VEGAnn	Jetpack (COCI16_jetpack)	C++14	80 / 80	34 ms	10488 KiB

jetpack

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