oj.uz

Submission #133388

# Submission time Handle Problem Language Result Execution time Memory
133388 2019-07-20T13:29:13 Z Zex Jetpack (COCI16_jetpack) C++11
80 / 80
 85 ms 11028 KB 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF INT_MAX
#define output for(int i=0;i<sizex;i++) { for(int j=0;j<sizey;j++) { cout << moveChart[i][j] << " "; }cout<<endl; }cout<<endl;

struct el{
    int s; int dur;

    el(){}
    el( int _s, int _d ){ s = _s; dur = _d; }
};

const int maxN = 10;
const int maxM = 100000;
const int N = 10; int M;
bool vis[maxN][maxM];
bool bt[maxN][maxM]; // 1 - HOLD   0 - LET GO
int PREV[maxN][maxM];
char mat[maxN][maxM];

bool dir( int a, int b ){

    if( a == b ){
        return a == N-1;
    }
    return b < a;

}

void f( int H, int n, int PRH ){

    if( vis[H][n] || mat[H][n] == 'X' ) return;
    vis[H][n] = true;
    bt[H][n] = dir( H, PRH );
    PREV[H][n] = PRH;
    // cout << H << " " << n << " " << PRH << endl;

    if( n == M-1 ) return;

    if( H == N-1 ){
        f( H, n+1, H );
        f( H-1, n+1, H ); 
    }else if( H == 0 ){
        f( H+1, n+1, H );
        f( H, n+1, H );
    }else{
        f( H+1, n+1, H );
        f( H-1, n+1, H );
    }

}

void findPath( int H ){

    int n = M-1;
    int dur = 0;
    bool b;
    vector <el> res;
    vector <int> debug;

    do{

        // cout << H << " " << n << endl;

        b = bt[H][n];
        debug.push_back(b);
        if( b ) { dur++; }
        else{
            if( dur ) res.push_back( el( n, dur ) );
            dur = 0;
        } 
        H = PREV[H][n];
        n--;

    }while( n >= 0 );

    cout << res.size() << endl;
    for(int i=res.size()-1;i>=0;i--){
        cout << res[i].s << " " << res[i].dur << endl;
    }
    
    // reverse( debug.begin(), debug.end() );
    // for(int i=0;i<debug.size();i++) cout << debug[i] << " "; cout << endl;

}

int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    memset( vis, 0, sizeof vis );
    memset( PREV, -1, sizeof PREV );

    cin >> M;

    for(int i=N-1;i>=0;i--) for(int j=0;j<M;j++) cin >> mat[i][j];

    f( 0, 0, N );

    for(int i=0;i<N;i++){
        if( vis[i][M-1] ){ findPath( i ); break; }
    }

}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5368 KB Output is correct
2 Correct 6 ms 5368 KB Output is correct
3 Correct 6 ms 5368 KB Output is correct
4 Correct 7 ms 5368 KB Output is correct
5 Correct 8 ms 5624 KB Output is correct
6 Correct 9 ms 5752 KB Output is correct
7 Correct 18 ms 6520 KB Output is correct
8 Correct 33 ms 8248 KB Output is correct
9 Correct 52 ms 9784 KB Output is correct
10 Correct 85 ms 11028 KB Output is correct