Submission #702390

#	Time	Username	Problem	Language	Result	Execution time	Memory
702390		delrey	Jetpack (COCI16_jetpack)	C++14	80 / 80	120 ms	4052 KiB

jetpack

#include <bits/stdc++.h>

using namespace std;

int n;
char c[10][100000];
bool dp[10][100000];
vector < pair<int, int> > moves;

int main()
{
    cin>>n;
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < n; j++)
            cin>>c[i][j];
    dp[9][0] = true;
    for(int j = 1; j < n; j++)
    {
        if(c[0][j] == '.')
            dp[0][j] = dp[0][j - 1];
        if(c[9][j] == '.')
            dp[9][j] = dp[9][j - 1];
        for(int i = 0; i < 9; i++)
            if(c[i][j] == '.')
                dp[i][j] = dp[i + 1][j - 1] || dp[i][j];
        for(int i = 1; i < 10; i++)
            if(c[i][j] == '.')
                dp[i][j] = dp[i - 1][j - 1] || dp[i][j];
    }
    int y = 9;
    while(!dp[y][n - 1])
        y--;
    for(int x = n - 1; x > 0; x--)
    {
        if(y == 9)
        {
            if(dp[y - 1][x - 1])
                y--;
            continue;
        }
        if(y == 0)
        {
            if(dp[y + 1][x - 1])
                y++;
            moves.push_back({x - 1, 1});
            continue;
        }
        if(dp[y + 1][x - 1])
        {
            moves.push_back({x - 1, 1});
            y++;
        }
        else
            y--;
        //cout<<y<<" ";
    }
    //cout<<endl;
    reverse(moves.begin(), moves.end());
    cout<<moves.size()<<endl;
    for(auto i : moves)
        cout<<i.first<<" "<<i.second<<endl;
    /*
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(dp[i][j])
                cout<<"*";
            else
                cout<<c[i][j];
        }
        cout<<endl;
    }
    */
    return 0;
}

• Subtask 1: 80 / 80