Submission #1025976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025976		model_code	Text editor (CEOI24_editor)	C++17	56 / 100	2218 ms	1048576 KiB

Main

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

typedef uint64_t u64;

struct node;

struct edge {
    u64 length;
    node *target;

    edge(u64 length, node *target) : length(length), target(target) {}
};

struct node {
    std::vector<edge> edges;
    bool visited = false;
};

struct coords {
    u64 row;
    u64 col;

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

struct compressor {
    std::vector<u64> values;

    void build() {
        std::sort(values.begin(), values.end());
        auto end = std::unique(values.begin(), values.end());
        values.erase(end, values.end());
    }

    u64 compress(u64 value) {
        return std::lower_bound(values.begin(), values.end(), value) - values.begin();
    }

    u64 decompress(u64 value) {
        return values[value];
    }
};

std::pair<node *, node *> build_graph(std::vector<u64> lines, coords start, coords end) {
    compressor com = {lines};
    com.values.push_back(start.col);
    com.values.push_back(end.col);
    com.values.push_back(0);
    com.build();

    std::vector<std::vector<node *>> nodes;

    for (u64 length : lines) {
        std::vector<node *> line;

        node *last = new node;
        line.push_back(last);

        u64 com_length = com.compress(length);

        for (u64 i = 0; i < com_length; i++) {
            node *curr = new node;
            line.push_back(curr);

            u64 diff = com.decompress(i + 1) - com.decompress(i);

            curr->edges.push_back(edge(diff, last));
            last->edges.push_back(edge(diff, curr));

            last = curr;
        }

        nodes.push_back(line);
    }

    for (u64 line = 0; line < nodes.size(); line++) {
        for (u64 col = 0; col < nodes[line].size(); col++) {
            if (line > 0) {
                u64 other_col = std::min(col, nodes[line - 1].size() - 1);
                nodes[line][col]->edges.push_back(edge(1, nodes[line - 1][other_col]));
            }

            if (line < nodes.size() - 1) {
                u64 other_col = std::min(col, nodes[line + 1].size() - 1);
                nodes[line][col]->edges.push_back(edge(1, nodes[line + 1][other_col]));
            }
        }
    }

    for (u64 line = 0; line < nodes.size() - 1; line++) {
        nodes[line].back()->edges.push_back(edge(1, nodes[line + 1].front()));
        nodes[line + 1].front()->edges.push_back(edge(1, nodes[line].back()));
    }

    return {nodes[start.row][com.compress(start.col)], nodes[end.row][com.compress(end.col)]};
}

typedef std::pair<u64, node *> node_info;

u64 find_path(node *start, node *end) {
    std::priority_queue<node_info, std::vector<node_info>, std::greater<node_info>> queue;

    queue.push({0, start});

    while (!queue.empty()) {
        auto [dist, n] = queue.top();
        queue.pop();

        if (n->visited)
            continue;

        n->visited = true;

        if (n == end)
            return dist;

        for (edge e : n->edges) {
            queue.push({dist + e.length, e.target});
        }
    }

    return -1;
}

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

    u64 line_count;
    std::cin >> line_count;

    coords start;
    coords end;

    std::cin >> start.row >> start.col;
    std::cin >> end.row >> end.col;

    start.row--;
    start.col--;
    end.row--;
    end.col--;

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

    for (u64 i = 0; i < line_count; i++) {
        u64 length;
        std::cin >> length;

        lines.push_back(length);
    }

    auto nodes = build_graph(lines, start, end);
    std::cout << find_path(nodes.first, nodes.second) << std::endl;
}

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