제출 #1306680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306680		chrisvilches	Walk (CEOI06_walk)	C++20	100 / 100	340 ms	47376 KiB

walk

#include <bits/stdc++.h>
using namespace std;

struct Point {
  int x, y;
  Point operator-(const Point p) const { return {x - p.x, y - p.y}; }
  void operator+=(const Point p) {
    x += p.x;
    y += p.y;
  }
  bool operator<(const Point p) const { return x < p.x || (x == p.x && y < p.y); }
  int dist(const Point p) const { return abs(p.x - x) + abs(p.y - y); }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  Point dest;
  while (cin >> dest.x >> dest.y >> n) {
    vector<tuple<int, int, int, int>> events;

    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);

      events.emplace_back(x1 - 1, 1, y1 - 1, y2 + 1);
      events.emplace_back(x2 + 1, 0, y1 - 1, y2 + 1);
    }

    // TODO: This is weird. Make the ordering more explicit as to why it works that way.
    const int DEST = -1;
    events.emplace_back(dest.x, DEST, dest.y, dest.y);

    sort(events.begin(), events.end());

    map<int, Point> m;

    map<Point, Point> prev_point;

    // TODO: Find a better infinity value. Or try to get rid of it.
    const int inf = 1e8;

    m[0] = {0, 0};
    // TODO: This data is weird lmao
    m[-inf] = {-inf, -inf};
    m[inf] = {-inf, inf};

    // TODO: Maybe I can index distances by Y only.
    map<Point, int> dist;
    dist[{0, 0}] = 0;

    const auto update = [&](const Point p) {
      const auto it0 = m.lower_bound(p.y);
      const auto it1 = it0->first == p.y ? it0 : prev(it0);

      for (const auto it : {it0, it1}) {
        const Point point = it->second;

        // TODO: This looks like a Dijkstra implementation, but it's not, so make it
        // adhoc (on purpose).
        const int alt = dist[point] + p.dist(point);

        if (!dist.count(p) || dist[p] > alt) {
          prev_point[p] = point;
          dist[p] = alt;
        }
      }

      m[p.y] = p;
    };

    for (const auto& [x, type, y1, y2] : events) {
      // TODO: This is kinda shit.
      if (type == DEST) {
        update({x, y1});
        break;
      } else {
        update({x, y1});
        update({x, y2});
      }

      while (true) {
        const auto it = m.lower_bound(y1 + 1);
        if (y2 <= it->first) break;
        m.erase(it);
      }
    }

    vector<Point> path;
    Point curr = dest;

    while (curr.x != 0 || curr.y != 0) {
      path.emplace_back(curr);
      curr = prev_point[curr];
    }

    path.emplace_back(curr);

    reverse(path.begin(), path.end());

    vector<Point> deltas;

    const auto add_delta = [&](const Point d) {
      if (!deltas.empty() &&
          ((deltas.back().x == 0 && d.x == 0) || (deltas.back().y == 0 && d.y == 0))) {
        deltas.back() += d;
      } else {
        deltas.emplace_back(d);
      }
    };

    for (size_t i = 0; i + 1 < path.size(); i++) {
      const Point d = path[i + 1] - path[i];

      if (d.x != 0 && d.y != 0) {
        add_delta({d.x, 0});
        add_delta({0, d.y});
      } else {
        add_delta(d);
      }
    }

    int total_len = 0;

    for (const Point d : deltas) {
      total_len += d.x;
      total_len += abs(d.y);
    }

    cout << total_len << endl;

    cout << deltas.size() << endl;

    for (const Point d : deltas) {
      cout << d.x << ' ' << d.y << endl;
    }
  }
}

• Subtask 1: 100 / 100