제출 #1219383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219383		dizzy_groovy	Walk (CEOI06_walk)	C++20	100 / 100	154 ms	7956 KiB

walk

#include <bits/stdc++.h>

using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    vector<pair<pair<int, int>, pair<int, int>>> que;
    que.push_back({{x, 0}, {y + 1, y}});
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        que.push_back({{x1 - 1, 1}, {y1, y2}});
        que.push_back({{x2 + 1, -1}, {y1, y2}});
    }
    //set<pair<int, int>> s;
    vector<pair<int, int>> cur; // y x
    vector<int> p;
    cur.push_back({0, 0});
    p.push_back(-1);
    sort(que.begin(), que.end());
    set<pair<int, pair<int, int>>> s; // x dist ind
    set<int> s2;
    s2.insert(1e9);
    s.insert({0, {0, 0}});
    int sti = -1;
    int lans = -1;
    for (auto &i : que) {
        if (i.first.second == -1) {
            s2.erase(i.second.first - 1);
            s2.erase(i.second.second);
            continue;
        }
        pair<int, int> dist1 = {1e7, 1e7};
        pair<int, int> dist2 = {1e7, 1e7};
        int x1 = i.second.first - 1;
        int x2 = i.second.second + 1;
        auto tmp1 = s.lower_bound(make_pair(x1, make_pair(-1, -1)));
        if (tmp1 != s.end()) {
            if (*(s2.lower_bound(min(x1, tmp1->first))) >= max(x1, tmp1->first)) dist1 = min(dist1, {abs(x1 - tmp1->first) + tmp1->second.first, tmp1->second.second}); 
        }
        if (tmp1 != s.begin()) {
            tmp1 = prev(tmp1);
            if (*(s2.lower_bound(min(x1, tmp1->first))) >= max(x1, tmp1->first)) dist1 = min(dist1, {abs(x1 - tmp1->first) + tmp1->second.first, tmp1->second.second}); 
        }
        if (i.first.second == 0) {
            lans = dist1.first;
            sti = dist1.second;
            break;
        }
        auto tmp2 = s.lower_bound(make_pair(x2, make_pair(-1, -1)));
        if (tmp2 != s.end()) {
            if (*(s2.lower_bound(min(x2, tmp2->first))) >= max(x2, tmp2->first)) dist2 = min(dist2, {abs(x2 - tmp2->first) + tmp2->second.first, tmp2->second.second}); 
        }
        if (tmp2 != s.begin()) {
            tmp2 = prev(tmp2);
            if (*(s2.lower_bound(min(x2, tmp2->first))) >= max(x2, tmp2->first)) dist2 = min(dist2, {abs(x2 - tmp2->first) + tmp2->second.first, tmp2->second.second}); 
        }
        int ind1 = cur.size();
        cur.push_back({x1, i.first.first});
        int ind2 = cur.size();
        cur.push_back({x2, i.first.first});
        p.push_back(dist1.second);
        p.push_back(dist2.second);
        auto it = s.lower_bound(make_pair(x1, make_pair(-1, -1)));
        while (it != s.end() && it->first <= x2) {
            s.erase(it);
            it = s.lower_bound(make_pair(x1, make_pair(-1, -1)));
        }
        s2.insert(i.second.first - 1);
        s2.insert(i.second.second);
        s.insert({x1, {dist1.first, ind1}});
        s.insert({x2, {dist2.first, ind2}});
    }
    vector<pair<int, int>> path1;
    path1.push_back({x, y});
    while (sti != -1) {
        int x1 = cur[sti].second;
        int y1 = cur[sti].first;
        path1.push_back({path1.back().first, y1});
        path1.push_back({x1, y1});
        sti = p[sti];
    }
    reverse(path1.begin(), path1.end());
    vector<pair<int, int>> path2;
    int tmp = -1;
    for (int i = 1; i < path1.size(); i++) {
        if (path1[i] == path1[i - 1]) continue;
        if (path1[i].first == path1[i - 1].first) {
            if (tmp == 1) {
                path2.back().second += path1[i].second - path1[i - 1].second;
            } else {
                path2.push_back({0, path1[i].second - path1[i - 1].second});
            }
            tmp = 1;
        } else {
            if (tmp == 0) {
                path2.back().first += path1[i].first - path1[i - 1].first;
            } else {
                path2.push_back({path1[i].first - path1[i - 1].first, 0});
            }
            tmp = 0;
        }
    }
    cout << lans + x << "\n";
    cout << path2.size() << "\n";
    for (auto &i : path2) {
        cout << i.first << " " << i.second << "\n";
    }
}

• Subtask 1: 100 / 100