Submission #133388

#	Time	Username	Problem	Language	Result	Execution time	Memory
133388		Zex	Jetpack (COCI16_jetpack)	C++11	80 / 80	85 ms	11028 KiB

jetpack

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