Submission #1084660

#TimeUsernameProblemLanguageResultExecution timeMemory
1084660SulAText editor (CEOI24_editor)C++17
19 / 100
83 ms41016 KiB
#include <bits/stdc++.h>
using namespace std;

void subtask_2(int n) {
    pair<int,int> start, end;
    cin >> start.first >> start.second >> end.first >> end.second;

    int l[n+1]; for (int i = 1; i <= n; i++) {
        cin >> l[i];
        l[i]++;
    }

    int dist[n+1][5002];
    bool vis[n+1][5002] = {};
    queue<pair<int,int>> q;
    q.push(start);
    vis[start.first][start.second] = true;
    dist[start.first][start.second] = 0;

    auto visit = [&](int to_x, int to_y, int from_x, int from_y) {
        if (!vis[to_x][to_y]) {
            dist[to_x][to_y] = dist[from_x][from_y] + 1;
            vis[to_x][to_y] = true;
            q.emplace(to_x, to_y);
        }
    };

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

        // left
        if (x != 1 || y != 1) {
            int l_x, l_y;
            if (y == 1) {
                l_x = x - 1;
                l_y = l[x - 1];
            } else {
                l_x = x;
                l_y = y - 1;
            }
            visit(l_x, l_y, x, y);
        }

        // right
        if (x != n || y != 1) {
            int r_x, r_y;
            if (y == l[x]) {
                r_x = x + 1;
                r_y = 1;
            } else {
                r_x = x;
                r_y = y + 1;
            }
            visit(r_x, r_y, x, y);
        }

        // up
        if (x != 1) {
            visit(x - 1, min(y, l[x - 1]), x, y);
        }

        // down
        if (x != n) {
            visit(x + 1, min(y, l[x + 1]), x, y);
        }
    }
    cout << dist[end.first][end.second];
}

#define int long long
int find_dist(int s, int e, int len) {
    return min({
       (s - e + len) % len,
       (e - s + len) % len
    });
}

void subtask_1() {
    int s_row, s_col, e_row, e_col, l;
    cin >> s_row >> s_col >> e_row >> e_col >> l;
    l++;

    if (e_row == 2) { // end is row 2
        cout << (s_row == 1 ? 1 : 0);
    } else if (s_row == 1) { // both on row 1
        cout << min({
            find_dist(s_col, e_col, l),
            2 + find_dist(1, e_col, l),
            2 + find_dist(l, e_col, l)
        });
    } else {
        cout << 1 + min({
            find_dist(1, e_col, l),
            find_dist(l, e_col, l)
        });
    }
#undef int
}

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

    int n; cin >> n;
    if (n == 2) subtask_1();
    else if (n <= 1000) subtask_2(n);
    else cout << rand();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...