Submission #1025972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025972		model_code	Text editor (CEOI24_editor)	C++17	100 / 100	263 ms	31556 KiB

Main

// Author: Benjamin Swart
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

using std::ptrdiff_t, std::size_t;
typedef uint64_t u64;

struct coords {
    u64 row;
    u64 col;

    constexpr coords(u64 row, u64 col) : row(row), col(col) {}
    constexpr coords() : row(0), col(0) {}
};

inline u64 abs_diff(u64 a, u64 b) {
    if (a > b)
        return a - b;
    else
        return b - a;
}

// Returns a vector such that result[target] is the minimum of all values between
// values[source] and values[target]. 
std::vector<u64> minimums_to(std::vector<u64> const &values, u64 source) {
    std::vector<u64> result(values.size());

    u64 minimum = values[source];

    for (size_t i = source; i < values.size(); i++) {
        minimum = std::min(minimum, values[i]);
        result[i] = minimum;
    }

    minimum = values[source];

    for (ptrdiff_t i = source - 1; i >= 0; i--) {
        minimum = std::min(minimum, values[i]);
        result[i] = minimum;
    }

    return result;
}

// Returns the length of the shortest path that doesn't leave the start line.
// This will often be +infinity.
u64 direct_path(std::vector<u64> const &lines, coords start, coords end) {
    auto rows = std::minmax(start.row, end.row);

    for (size_t i = rows.first; i <= rows.second; i++) {
        if (lines[i] < std::min(start.col, end.col))
            return std::numeric_limits<u64>::max();
    }

    return abs_diff(start.row, end.row) + abs_diff(start.col, end.col);
}

// Returns the length of the shortest path that consists of first pressing up and down only,
// followed by movement within the final line.
// Together with direct_path, these two function return the shortest path
// if the shortest path doesn't ever visit the first column.
u64 fall_path(std::vector<u64> const &lines, coords start, coords end) {
    std::vector<u64> mins_to_start = minimums_to(lines, start.row);
    std::vector<u64> mins_to_end = minimums_to(lines, end.row);

    u64 best = std::numeric_limits<u64>::max();

    for (size_t i = 0; i < lines.size(); i++) {
        u64 length = lines[i];

        if (length > start.col || length > mins_to_start[i] || length > mins_to_end[i])
            continue;

        u64 score = abs_diff(start.row, i) + abs_diff(end.row, i) + abs_diff(end.col, length);
        best = std::min(best, score);
    }

    return best;
}

// This function calulates the length of the shortest path that visits the first line.
u64 jump_path(std::vector<u64> const &lines, coords start, coords end) {
    std::vector<u64> mins_to_start = minimums_to(lines, start.row);
    std::vector<u64> mins_to_end = minimums_to(lines, end.row);

    std::vector<u64> dists_to_left(lines.size(), std::numeric_limits<u64>::max());

    // Calculates the fastest way to get to each position in the first column.
    for (size_t i = 0; i < lines.size(); i++) {
        u64 end_position = std::min(start.col, mins_to_start[i]);

        u64 dist_to_left = end_position + abs_diff(start.row, i);
        u64 dist_to_right = lines[i] - end_position + abs_diff(start.row, i);

        dists_to_left[i] = std::min(dists_to_left[i], dist_to_left);

        if (i < lines.size() - 1)
            dists_to_left[i + 1] = std::min(dists_to_left[i + 1], dist_to_right + 1);
    }

    // Accounts for movement within the first column.
    for (size_t i = 1; i < lines.size(); i++)
        dists_to_left[i] = std::min(dists_to_left[i], dists_to_left[i - 1] + 1);

    for (ptrdiff_t i = lines.size() - 2; i >= 0; i--)
        dists_to_left[i] = std::min(dists_to_left[i], dists_to_left[i + 1] + 1);

    u64 best = dists_to_left[end.row] + end.col;

    // Calculates the fastest way to get to the finish from each position in the first column.
    for (size_t i = 0; i < lines.size() - 1; i++) {
        u64 end_position = mins_to_end[i];
        u64 dist_to_right = dists_to_left[i + 1] + 1;
        u64 dist = dist_to_right + abs_diff(end.row, i) + abs_diff(end.col, end_position);

        best = std::min(best, dist);
    }

    return best;
}

u64 path(std::vector<u64> const &lines, coords start, coords end) {
    return std::min({
        direct_path(lines, start, end),
        fall_path(lines, start, end),
        jump_path(lines, start, end),
    });
}

int main() {
    std::cin.exceptions(std::cin.badbit | std::cin.failbit);

    u64 line_count;
    std::cin >> line_count;

    coords start;
    coords end;

    for (u64 *n : {&start.row, &start.col, &end.row, &end.col}) {
        std::cin >> *n;
        (*n)--;
    }

    std::vector<u64> lines(line_count);

    for (u64 &line : lines)
        std::cin >> line;

    std::cout << path(lines, start, end) << std::endl;
}

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