Submission #245688

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245688	2020-07-07T07:52:39 Z	Vladikus004	Jetpack (COCI16_jetpack)	C++14	80 / 80	18 ms	5888 KB

jetpack

#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 100000 + 3;
int n, can[10][N];
char a[10][N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    for (int i = 0; i < 10; i++)
        cin >> a[i];
    can[9][0] = 1;
    for (int j = 1; j < n; j++){
        for (int i = 0; i < 10; i++){
            if (a[i][j] == 'X') continue;
            int x1, y1, x2, y2;
            x1 = i - 1; y1 = j - 1;
            x2 = i + 1; y2 = j - 1;
            x1 = max(x1, 0);
            x2 = min(x2, 9);
            can[i][j] = max(can[x1][y1], can[x2][y2]);
        }
    }
//    for (int i = 0; i < 10; i++){
//        for (int j = 0; j < n; j++){
//            cout << can[i][j];
//        }
//        cout << '\n';
//    }
    int x;
    for (int i = 0; i < 10; i++)
    if (can[i][n - 1]){
        x = i;
    }
    vector <int> way;
    int last = 0;
    int j = n - 1;
    while (j){
        int x1, y1, x2, y2;
        x1 = x - 1; y1 = j - 1;
        x2 = x + 1; y2 = j - 1;
        --j;
        x1 = max(x1, 0);
        x2 = min(x2, 9);

        if (x == 9){
            way.push_back(0);
            if (!can[x2][y2]) x = 8;
            last = 0;
            continue;
        }

        if (x == 0){
            way.push_back(1);
            if (!can[x1][y1]) x = 1;
            last = 1;
            continue;
        }


        if (!last){
            if (can[x1][y1]) way.push_back(0);
            else way.push_back(1);
        }else{
            if (can[x2][y2]) way.push_back(1);
            else way.push_back(0);
        }
        last = way.back();
        if (last) x = min(x + 1, 9);
        else x = max(x - 1, 0);
    }
    reverse(all(way));
//    for (auto u: way) cout << u << " "; cout << "!\n";
    vector <pii> ans;
    int st = 0, sum = 0;
    last = 0;
    for (int i = 0; i < way.size(); i++){
        if (way[i] && last == 0){
            st = i;
            sum = 1;
        }else
        if (way[i] && last){
            sum++;
        }else
        if (!way[i] && last){
            ans.push_back({st, sum});
        }
        last = way[i];
    }
    cout << ans.size() << "\n";
    for (auto u: ans) cout << u.first << " " << u.second << "\n";
}

Compilation message

jetpack.cpp: In function 'int main()':
jetpack.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < way.size(); i++){
                     ~~^~~~~~~~~~~~
jetpack.cpp:57:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (x == 9){
         ^~

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	512 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct
7	Correct	7 ms	1664 KB	Output is correct
8	Correct	9 ms	3200 KB	Output is correct
9	Correct	14 ms	4608 KB	Output is correct
10	Correct	18 ms	5888 KB	Output is correct