Submission #42119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
42119	2018-02-22T17:47:57 Z	wasyl	Jetpack (COCI16_jetpack)	C++11	80 / 80	26 ms	4756 KB

jetpack

#include <bits/stdc++.h>
#ifndef dbg
#define dbg(...)
#endif
#define all(x) begin(x), end(x)
#define rsz(...) resize(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define prt(...) print(cout, __VA_ARGS__)
#define dprt(...) dbg(print(cerr,__VA_ARGS__))
#define dmp(...) dprt(#__VA_ARGS__, '=', __VA_ARGS__)
using namespace std;using ll=long long;
template<typename t>using V=vector<t>;
template<typename t>void print(ostream& os, const t& a){os<<a<<'\n';}
template<typename t, typename... A>void print
(ostream& os, const t& a, A&&... b){os<<a<<' ';print(os, b...);}

int n;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    V< V< bool > > rt(10, V< bool >(n));
    V< V< bool > > tb(10, V< bool >(n));
    for (int i = 9; i >= 0; --i)
    {
        string s; cin >> s;
        for (int k = 0; k < n; ++k)
            tb[i][k] = s[k] == '.';
    }

    queue< pair< int, int > > Q;
    rt[0][0] = true;
    Q.push({0, 0});
    while (!Q.empty())
    {
        auto p = Q.front(); Q.pop();
//        dprt(p.first, p.second);
        if (p.second == n - 1)
            continue;
        if (p.first > 0 and rt[p.first - 1][p.second + 1] == false and
        tb[p.first - 1][p.second + 1] == true)
        {
            rt[p.first - 1][p.second + 1] = true;
            Q.push({p.first - 1, p.second + 1});   
        }
        if (p.first < 9 and rt[p.first + 1][p.second + 1] == false and
        tb[p.first + 1][p.second + 1] == true)
        {
            rt[p.first + 1][p.second + 1] = true;
            Q.push({p.first + 1, p.second + 1});
        }
        if ((p.first == 0 or p.first == 9) 
        and rt[p.first][p.second + 1] == false and
        tb[p.first][p.second + 1] == true)
        {
            rt[p.first][p.second + 1] = true;
            Q.push({p.first, p.second + 1});
        }
    
    }
dbg(
    for (int i = 9; i >= 0; --i)
    {
        for (int k = 0; k < n; ++k)
            cerr << (rt[i][k]);
        cerr << '\n';
    }
);

    int x = 0, y = n - 1;
    while (rt[x][y] == false)
        ++x;
    
    dmp(x, y);
    V< pair< int, int > > ph;
    ph.psh({x, y});
    while (x != 0 or y != 0)
    {
        if (x > 0 and rt[x - 1][y - 1])
        {
            ph.psh({x - 1, y - 1});
            --x, --y;
        }
        else if (x < 9 and rt[x + 1][y - 1])
        {
            ph.psh({x + 1, y - 1});
            ++x, --y;
        }
        else if ((x == 0 or x == 9) and rt[x][y - 1])
        {
            ph.psh({x, y - 1});
            --y;
        }
    }

    reverse(all(ph));
    
dbg(
    for (auto& p : ph)
        dprt(p.first, p.second);
);
    V< pair< int, int > > odp;
    for (int i = 0; i < ph.size(); ++i)
    {
        if (i < ph.size() - 1 and (ph[i].first < ph[i + 1].first or
        (ph[i].first == 9 and ph[i + 1].first == 9)))
        {
            int pt = i + 1;
            while (pt < ph.size() - 1 and 
            (ph[pt].first < ph[pt + 1].first or(ph[pt].first == 9 and
            ph[pt + 1].first == 9)))
                ++pt;
            odp.psh({i, pt - i});
            i = pt;
        }
    }
    prt(odp.size());
    for (auto& p : odp)
        prt(p.first, p.second);

}

Compilation message

jetpack.cpp: In function 'int main()':
jetpack.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ph.size(); ++i)
                       ^
jetpack.cpp:108:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < ph.size() - 1 and (ph[i].first < ph[i + 1].first or
               ^
jetpack.cpp:112:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (pt < ph.size() - 1 and 
                       ^

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	452 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	3 ms	648 KB	Output is correct
6	Correct	4 ms	804 KB	Output is correct
7	Correct	8 ms	1400 KB	Output is correct
8	Correct	17 ms	2208 KB	Output is correct
9	Correct	23 ms	3432 KB	Output is correct
10	Correct	26 ms	4756 KB	Output is correct