Submission #641410

#	Time	Username	Problem	Language	Result	Execution time	Memory
641410		LeThanhMinh	Jetpack (COCI16_jetpack)	C++14	0 / 80	71 ms	17868 KiB

jetpack

#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);
        
    }
    
}

• Subtask 1: 0 / 80