Submission #241376

#	Time	Username	Problem	Language	Result	Execution time	Memory
241376		kartel	Jetpack (COCI16_jetpack)	C++14	80 / 80	44 ms	9720 KiB

jetpack

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +200500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e9)
#define el '\n'
#define pii pair <int, int>
#define err ld(1e-9)
#define last(x) x.back()
#define all(x) (x.begin(), x.end())
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
 
int x, y, ex, ey, Hold, hold, st, i, j, n, m, sx, sy, est;
vector <pair <int, int> > ans;
pair <int, int> pr[11][N];
queue <pair < pair <int, int>, pair <int, int> > > q;
bool mrk[11][N], f = 0;
 
void put(int x, int y, int st, int hold)
{
    if (f) ex = x, est = st, Hold = hold;
 
    q.push({{x, y}, {st, hold}});
    mrk[x][y] = 1;
}
 
void get(int &x, int &y, int &st, int &hold)
{
    x = q.front().F.F;
    y = q.front().F.S;
    st = q.front().S.F;
    hold = q.front().S.S; q.pop();
}
 
void putall(int x, int y, int st, int hold)
{
    int steps[3][2] = {{1, 1}, {0, 1}, {-1, 1}};
 
    for (int i = 0; i < 3 && !f; i++)
    {
        int cx = x + steps[i][0];
        int cy = y + steps[i][1];
        int nhold = hold;
        if (cx < 1 || cx > n || cy < 1 || cy > m) continue;
        if (steps[i][0] == 0 && (x != n && x != 1)) continue;
 
        if (steps[i][0] == 0 && x == 1) nhold++;
        else if (steps[i][0] == -1) nhold++;
        else nhold = 0;
 
        if (mrk[cx][cy]) continue;
 
        if (cy == m) f = 1;
 
        pr[cx][cy] = {x, hold};
 
        put(cx, cy, st, nhold);
    }
}
 
void restore()
{
    ey = m;
    st = est;
    hold = 0;
 
    while (ey != 1)
    {
        if (pr[ex][ey].S == Hold - 1) hold++;
 
        if (pr[ex][ey].S == Hold - 1 && pr[ex][ey].S == 0)
            ans.pb({st - 1, hold}), hold = 0;
 
        Hold = pr[ex][ey].S;
 
        st--;
        ex = pr[ex][ey].F;
        ey--;
    }
 
    reverse(ans.begin(), ans.end());
}
 
int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    in("input.txt");
//    out("output.txt");
 
    cin >> m;
    n = 10;
 
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
    {
        char c;
        cin >> c;
 
        mrk[i][j] = 0;
 
        if (c == 'X')
            mrk[i][j] = 1;
    }
 
    sx = n;
    sy = 1;
    hold = 0;
 
    put(sx, sy, 0, hold);
 
    while (!f)
    {
        get(x, y, st, hold);
 
        st++;
 
        putall(x, y, st, hold);
    }
 
    restore();
 
    cout << sz(ans) << el;
    for (auto x : ans) cout << x.F << " " << x.S << el;
}
 
//
//00000
//00110
//00111
//00011
//00000

• Subtask 1: 80 / 80