| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 133387 | Zex | Jetpack (COCI16_jetpack) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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; }
}
}