Submission #1213531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213531		spetr	Text editor (CEOI24_editor)	C++20	14 / 100	1633 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    ll sy, sx;
    ll ey, ex;
    cin >> n;
    cin >> sy >> sx;
    cin >> ey >> ex;
    vector<ll> lines(n);
    for (ll i = 0; i < n; i++) {
        cin >> lines[i];
    }

    // Zero-based indices
    sx--; sy--;
    ex--; ey--;

    // If start == end
    if (sx == ex && sy == ey) {
        cout << 0;
        return 0;
    }

    auto encode = [&](ll x, ll y) {
        return (y << 32) | x;
    };

    queue<array<ll,3>> q;
    q.push({sx, sy, 0});
    unordered_set<ll> visited;
    visited.reserve(n * 2);

    while (!q.empty()) {
        auto [x, y, dist] = q.front();
        q.pop();

        // Move left
        {
            ll nx = x, ny = y;
            if (x > 0) {
                nx = x - 1;
            } else if (x == 0 && y > 0) {
                ny = y - 1;
                nx = lines[ny];
            } else {
                nx = -1; // invalid
            }
            if (nx >= 0) {
                ll code = encode(nx, ny);
                if (visited.find(code) == visited.end()) {
                    if (nx == ex && ny == ey) {
                        cout << dist + 1;
                        return 0;
                    }
                    visited.insert(code);
                    q.push({nx, ny, dist + 1});
                }
            }
        }

        // Move right
        {
            ll nx = x, ny = y;
            if (x < lines[y]) {
                nx = x + 1;
            } else if (x == lines[y] && y < n - 1) {
                ny = y + 1;
                nx = 0;
            } else {
                nx = -1; // invalid
            }
            if (nx >= 0) {
                ll code = encode(nx, ny);
                if (visited.find(code) == visited.end()) {
                    if (nx == ex && ny == ey) {
                        cout << dist + 1;
                        return 0;
                    }
                    visited.insert(code);
                    q.push({nx, ny, dist + 1});
                }
            }
        }

        // Move up
        if (y > 0) {
            ll ny = y - 1;
            ll nx = x > lines[ny] ? lines[ny] : x;
            ll code = encode(nx, ny);
            if (visited.find(code) == visited.end()) {
                if (nx == ex && ny == ey) {
                    cout << dist + 1;
                    return 0;
                }
                visited.insert(code);
                q.push({nx, ny, dist + 1});
            }
        }

        // Move down
        if (y < n - 1) {
            ll ny = y + 1;
            ll nx = x > lines[ny] ? lines[ny] : x;
            ll code = encode(nx, ny);
            if (visited.find(code) == visited.end()) {
                if (nx == ex && ny == ey) {
                    cout << dist + 1;
                    return 0;
                }
                visited.insert(code);
                q.push({nx, ny, dist + 1});
            }
        }
    }

    return 0;
}

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