답안 #641410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641410 2022-09-16T16:11:50 Z LeThanhMinh Jetpack (COCI16_jetpack) C++14
0 / 80
71 ms 17868 KB
#include <bits/stdc++.h>

#define ii pair<int, int>
#define fs first
#define sc second

using namespace std;

const int N = 1e5 + 1;

int n;

int can[11][N];
ii pa[11][N];
int res[N];

string grid[N];

void print(int x, int y) {
    
    res[y] = x;

    ii zero = {0, 0};
    
    while (pa[x][y] != zero) {
        
        ii tem = pa[x][y];
        x = tem.fs, y = tem.sc;
        res[y] = x;

    }
    
    queue<ii> ans;
    
    int times = 0;
    
    int start = -1, t = 0;
    
    for (int i = 2; i < n; i++) {
        
        if (res[i] <= res[i+1]) {
            
            if (start == -1) start = i;
            t++;
            
        } else {
            
            if (start == -1) continue;
            
            ans.push({start, t});
            start = -1, t = 0;
            times++;
            
        }
        
    }
    
    if (start != -1) {
        
        ans.push({start, t});
        times++;   
    }
    
    cout << times << endl;
    
    while (ans.size()) {
        
        ii tem = ans.front(); ans.pop();
        cout << tem.fs - 1 << " " << tem.sc << endl;
        
    }
    
    
    exit(0);
    
}

signed main() {
    
    cin >> n;
    
    for (int i = 10; i > 0; i--) {
        
        string s; cin >> s;
        s = "~" + s;
        grid[i] = s;
        
    }
    
    can[1][2] = 1;
    
    for (int c = 3; c <= n; c++) {
        for (int r = 1; r <= 10; r++) {
            
            if (grid[r][c] == 'X') {
                
                continue;
                
            }
            if (r == 10) {
                
                can[r][c] = can[r-1][c-1] || can[r][c-1];
                
                if (can[r-1][c-1]) pa[r][c] = {r-1, c-1};
                else if (can[r][c-1]) pa[r][c] = {r, c-1};
                
            } else if (r == 1) {
                
                can[r][c] = can[r+1][c-1] || can[r][c-1];
                
                if (can[r+1][c-1]) pa[r][c] = {r+1, c-1};
                else if (can[r][c-1]) pa[r][c] = {r, c-1};
                
            } else {
                
                can[r][c] = can[r+1][c-1] || can[r-1][c-1];
                
                if (can[r+1][c-1]) pa[r][c] = {r+1, c-1};
                else if (can[r-1][c-1]) pa[r][c] = {r-1, c-1};
                
            }
            
        }
        
    }
    
    for (int i = 10; i > 0; i--) {
        
        if (can[i][n]) print(i, n);
        
    }
    
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3540 KB Crashed with an obstacle
2 Incorrect 2 ms 3440 KB Crashed with an obstacle
3 Incorrect 2 ms 3540 KB Crashed with an obstacle
4 Incorrect 3 ms 3668 KB Crashed with an obstacle
5 Incorrect 6 ms 4180 KB Crashed with an obstacle
6 Incorrect 7 ms 4436 KB Crashed with an obstacle
7 Incorrect 16 ms 6268 KB Crashed with an obstacle
8 Incorrect 40 ms 10476 KB Crashed with an obstacle
9 Incorrect 52 ms 13924 KB Crashed with an obstacle
10 Incorrect 71 ms 17868 KB Crashed with an obstacle