Submission #366568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366568	2021-02-14T14:41:09 Z	maozkurt	Jetpack (COCI16_jetpack)	C++17	80 / 80	370 ms	14700 KB

jetpack

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn = 1e5+5;
string mat[15];
int ne[maxn][15];
bool nebb[maxn][15];

int n;
int start = -1;
bool f(int col, int row, bool bastik){
    if(row < 0 || row > n-1)
        return false;
    if(mat[row][col] == 'X')
        return false;

    // cerr << col << sp << row << sp << bastik << endl;

    if(col == n-1){
        return true;  
    }

    if(bastik){
        if(row == 0){
            if(f(col+1, row,true)){
                ne[col][row] = 0;
                nebb[col][row] = true;
                return true;
            }
            else if(f(col+1,row+1,false)){
                ne[col][row] = 1;
                nebb[col][row] = false;
                return true;
            }
        }
        else if(row == 9){
            abort();
            if(f(col+1,row-1,true)){
                ne[col][row] = -1;
                nebb[col][row] = true;
                return true;
            }
            else if(f(col+1,row,false)){
                ne[col][row] = 0;
                nebb[col][row] = false;
                return true;
            }
        }
        else{
            if(f(col+1,row-1,true)){
                ne[col][row] = -1; 
                nebb[col][row] = true;
                return true;
            }
            else if(f(col+1,row+1,false)){
                ne[col][row] = 1;
                nebb[col][row] = false;
                return true;
            }
        }
    }
    else{
        if(row == 0){
            abort();
        }
        else if(row == 9){
            if(f(col+1,row,false)){
                ne[col][row] = 0;
                nebb[col][row] = false;
                return true;
            }
            else if(f(col+1, row-1, true)){
                ne[col][row] = -1;
                nebb[col][row] = true;
                return true;
            }

        }
        else{
            if(f(col+1,row+1,false)){
                ne[col][row] = 1;
                nebb[col][row] = false;
                return true;
            }
            else if(f(col+1,row-1,true)){
                ne[col][row] = -1;
                nebb[col][row] = true;
                return true;
            }
        }
    }
    return false;
}

int main(){

    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
    cin>>n; 
    for(int i=0;i<10;i++){
        cin >> mat[i];
    }

    assert(f(0,9,false));

    vector<pii> way;
    int row = 9;
    pii cur = {-1,-1};
    for(int col=0;col<n;col++){
        if(nebb[col][row] && cur.ff == -1){
            cur.ff = col;
        }
        else if(!nebb[col][row] && cur.ff != -1){
            cur.ss = col - cur.ff;
            way.pb(cur);
            cur = {-1,-1};
        }
        row += ne[col][row];
    }
    if(cur.ff!=-1){
        way.pb({cur.ff,n-cur.ff});
    }
    
    cout << way.size() << endl;
    for(pii i : way){
        cout << i.ff << sp << i.ss << endl;
    }

}

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	1 ms	1004 KB	Output is correct
6	Correct	14 ms	1260 KB	Output is correct
7	Correct	73 ms	3180 KB	Output is correct
8	Correct	246 ms	7200 KB	Output is correct
9	Correct	370 ms	10872 KB	Output is correct
10	Correct	22 ms	14700 KB	Output is correct