Submission #1025973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025973		model_code	Text editor (CEOI24_editor)	C++17	14 / 100	424 ms	1048576 KiB

Main

// Author: Tymofii Reizin
#include <iostream>
#include <vector>
#include <queue>
#include <array>

using namespace std;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    int sl, sc, el, ec;
    cin >> sl >> sc >> el >> ec;
    --sl;
    --sc;
    --el;
    --ec;
    vector<int> l(n);
    for (int &i : l)
        cin >> i;
    vector<vector<int>> dist(n);
    vector<vector<bool>> used(n);
    for (int i = 0; i < n; ++i)
    {
        dist[i].resize(l[i] + 1, (int)2e9 + 5);
        used[i].resize(l[i] + 1);
    }
    array<int, 4> dx{1, -1, 0, 0};
    array<int, 4> dy{0, 0, 1, -1};
    array<char, 4> move{'u', 'd', 'r', 'l'};
    auto check = [&l, n](int &x, int &y, char move) -> bool
    {
        if (x < 0 || x >= n)
            return false;

        if (y == -1 && move == 'l')
        {
            --x;
            if (x < 0)
                return false;
            y = l[x];
        }
        else if (y == l[x] + 1 && move == 'r')
        {
            ++x;
            if (x >= n)
                return false;
            y = 0;
        }
        else
            y = min(y, l[x]);
        return true;
    };
    queue<pair<int, int>> q;
    q.push({sl, sc});
    dist[sl][sc] = 0;
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        if (used[x][y])
            continue;
        used[x][y] = true;
        for (int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (check(nx, ny, move[i]))
            {
                dist[nx][ny] = min(dist[nx][ny], dist[x][y] + 1);
                q.push({nx, ny});
            }
        }
        if (dist[el][ec] != (int)2e9 + 5)
            break;
    }
    cout << dist[el][ec] << '\n';
    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