oj.uz

Submission #702390

# Submission time Handle Problem Language Result Execution time Memory
702390 2023-02-23T21:16:11 Z delrey Jetpack (COCI16_jetpack) C++14
80 / 80
 120 ms 4052 KB 
#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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 24 ms 1108 KB Output is correct
8 Correct 58 ms 2176 KB Output is correct
9 Correct 86 ms 3084 KB Output is correct
10 Correct 120 ms 4052 KB Output is correct