Submission #536686

#TimeUsernameProblemLanguageResultExecution timeMemory
536686ali22413836Jetpack (COCI16_jetpack)C++14
8 / 80
20 ms4180 KiB
#include <bits/stdc++.h> #define endl "\n" using namespace std ; typedef long long ll; typedef long double ld ; const int N=2e7; const ll inf=1e18 ; const ll mod = 1e9 + 7 ; ll mypower(ll x, ll y){ if(y == 0) return 1 ; if(y == 1) return x ; ll ret = mypower(x , y / 2); ret = (ret * ret) % mod; if(y % 2) ret = ( ret * x ) % mod ; return ret ; } ll n ; char a[20][100009] ; bool is2[20][100009] , is[20][100009] ; vector < pair < ll , ll > > ans ; ll la ; void sol(ll i , ll j , ll ti , ll len , ll iss){ a[i][j] = '*' ; if(iss == 0){ if(j == n - 1){ return ; } if(is2[i][j] && a[i - 1][j + 1] != 'X'){ la = ti ; sol(i - 1 , j + 1 , ti + 1 , len + 1 , 1) ; } else{ sol(i , j + 1 , ti + 1 , len , 0) ; } } else if(iss == 1){ if(j == n - 1){ ans.push_back({la , len}) ; return ; } if(is[i][j] && a[i + 1][j + 1] != 'X'){ ans.push_back({la , len}) ; la = 0 ; sol(i + 1 , j + 1 , ti + 1 , 0 , 2) ; } else if(i != 0 && a[i - 1][j + 1] != 'X'){ sol(i - 1 , j + 1 , ti + 1 , len + 1 , 1) ; } else{ sol(i , j + 1 , ti + 1 , len + 1 ,1) ; } } else{ if(j == n - 1){ return ; } if(is2[i][j] && a[i - 1][j + 1] != 'X'){ la = ti ; sol(i - 1 , j + 1 , ti + 1 , len + 1 , 1) ; } else if(i != 9 && a[i + 1][j + 1] !='X'){ sol(i + 1 ,j + 1 , ti + 1 , 0 , 2) ; } else if(i == 9 && a[i][j + 1] != 'X'){ sol(i , j + 1 , ti + 1 , 0 , 2) ; } } } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n ; for(int j = 0 ; j < 10 ; j++){ for(int i = 0 ; i < n ; i++){ cin >> a[j][i] ; } } is[0][n - 1] = is[9][n - 1] = 1 ; is2[0][n - 1] = is2[9][n - 1] = 1 ; for(int i = n - 1 ; i >= 0 ; i--){ is2[0][i] |= is2[0][i + 1] ; is[0][i] |= is[0][i + 1] ; is2[9][i] |= is2[9][i + 1] ; is[9][i] |= is[9][i + 1] ; } for(int j = n - 1 ; j >= 0 ; j--){ for(int i = 9 ; i >= 0 ; i--){ if(j == n - 1 && a[i][j] == '.'){ is[i][j] = is2[i][j] = 1 ; continue ; } if(a[i][j] == 'X'){ continue ; } is[i][j] = is[i + 1][j + 1] | is2[i + 1][j + 1] ; is2[i][j] = is2[i - 1][j + 1] | is[i - 1][j + 1] ; } } ll x = 9 , y = 0 , ti = 0 , len = 0 ; sol(x , y , ti , len , 0) ; cout << ans.size() << endl ; for(auto p : ans){ cout << p.first << " " << p.second << endl ; } // for(int i = 0 ; i < 10 ;i++){ // for(int j = 0 ; j< n ;j++){ // cout << a[i][j] ; // } // cout << endl ; // } // cout << a[9][0] << endl ; return 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...