Submission #1134503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134503		aliarapov	Text editor (CEOI24_editor)	C++20	0 / 100	2 ms	328 KiB

Main

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std; 
using namespace __gnu_pbds;

#define int long long
#define all(x) x.begin(),x.end() 
#define rall(x) x.rbegin(),x.rend()
           
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; } 

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;     

void solve() {
    int n, sx, sy, tx, ty;
    cin >> n >> sy >> sx >> ty >> tx;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    if (count(all(a), a[0]) == n) {
        auto dis = [](int fx, int fy, int ex, int ey) {
            return abs(fx - ex) + abs(fy - ey);
        };
        int ans = dis(sx, sy, tx, ty);
        if (sy != 1) chmin(ans, sx + dis(a[0] + 1, sy - 1, tx, ty));
        if (sy != n) chmin(ans, a[0] - sx + 2 + dis(1, sy + 1, tx, ty));
        cout << ans;
    } else {
        vector<vector<int> > dis(n);
        for (int i = 0; i < n; i++) dis[i].resize(a[i] + 1, 1e18);
        swap(sx, sy); swap(tx, ty);
        sx--, sy--, tx--, ty--;
        auto ok = [&](int x, int y) {
            if (0 <= x and x < n and 0 <= y and y <= a[x]) return 1;
            return 0;
        };
        queue<pair<int,int> > q;
        dis[sx][sy] = 0;
        q.push({sx, sy});
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for (auto [dx, dy] : {pair{1, 0}, {0, 1}, {-1, 0}, {0, -1}}) {
                int nx = dx + x, ny = dy + y;
                if (ok(nx, ny) and chmin(dis[nx][ny], dis[x][y] + 1)) {
                    q.push({nx, ny});
                }
            }
            if (y == 0 and x > 0 and chmin(dis[x - 1][a[x - 1]], dis[x][y] + 1)) {
                q.push({x - 1, a[x - 1]});
            }
            if (y == a[x] and x < n - 1 and chmin(dis[x + 1][0], dis[x][y] + 1)) {
                q.push({x + 1, 0});
            }
        }
        cout << dis[tx][ty];
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44