Submission #1306642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306642		chrisvilches	Walk (CEOI06_walk)	C++20	0 / 100	1098 ms	43408 KiB

walk

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

struct Point {
  int x, 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); }

  bool operator==(const Point p) const { return x == p.x && y == p.y; }
};

ostream& operator<<(ostream& os, const Point p) {
  return os << "(" << p.x << ", " << p.y << ")";
}

string polygon_to_str(const vector<Point>& polygon) {
  stringstream ss;
  ss << fixed << setprecision(6);
  ss << "polygon(";
  for (size_t i = 0; i < polygon.size(); i++) {
    if (i > 0) ss << ", ";
    ss << polygon[i];
  }
  ss << ")";
  return ss.str();
}

struct Segment {
  Point p, q;

  string to_desmos() const {
    stringstream ss;
    ss << fixed << setprecision(6) << "\\left(\\left(1-t\\right)\\cdot" << p.x + 0.5
       << "+t\\cdot" << q.x + 0.5 << ",\\left(1-t\\right)\\cdot" << p.y + 0.5
       << "+t\\cdot" << q.y + 0.5 << "\\right)";
    return ss.str();
  }
};

int main() {
  int n;
  Point dest;
  while (cin >> dest.x >> dest.y >> n) {
    cerr << endl << "---------------------------------------------" << endl << endl;
    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);
      // if (dest.x < x1) continue;

      // TODO: Maybe I can use each y independently on each event (no need to have both in
      // one item). I think I need to remove in the range, so I can't do that!!!
      events.emplace_back(x1 - 1, 1, y1 - 1, y2 + 1);
      events.emplace_back(x2 + 1, 0, y1 - 1, y2 + 1);

      vector<Point> poly;
      poly.emplace_back(x1, y1);
      poly.emplace_back(x2 + 1, y1);
      poly.emplace_back(x2 + 1, y2 + 1);
      poly.emplace_back(x1, y2 + 1);

      cerr << polygon_to_str(poly) << endl;
    }

    // TODO: what should the type be in this event????
    events.emplace_back(dest.x, -1, dest.y, dest.y);

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

    map<int, Point> m;

    map<Point, Point> prev_point;

    const int inf = 1e7;

    m[0] = {0, 0};
    // TODO: Maybe this will overflow in some cases.
    // TODO: This data is weird lmao
    // m[INT_MIN] = {0, -inf};
    // m[INT_MAX] = {0, inf};

    map<Point, int> dist;
    dist[{0, 0}] = 0;

    const auto update = [&](const int x, const int y) {
      // const auto it0 = m.lower_bound(y);
      // assert(it0 != m.end());
      // assert(it0 != m.begin());
      // const auto it1 = it0->first == y ? it0 : prev(it0);

      const Point p{x, y};
      // cerr << p << endl;
      if (prev_point.count(p)) return;

      // cerr << "trying to find prev for " << p << " (currently items in set: " <<
      // m.size()
      //      << ")" << endl;

      // Point point_to_use = prev_point[p];

      for (const auto& [_, point] : m) {
        // if (y == INT_MIN || y == INT_MAX) continue;
        // cerr << "    " << y << " : " << p << endl;

        const int alt = dist[point] + p.dist(point);
        assert(alt >= 0);
        // cerr << format("    dist[{}, {}] = {}", point.x, point.y, dist[point]) << endl;

        if (!dist.count(p) || dist[p] > alt) {
          prev_point[p] = point;
          dist[p] = alt;
          // cerr << "    setting " << point << endl;
        }
      }

      m[p.y] = p;

      // if (p.dist(it0->second) < p.dist(it1->second)) {
      //   // use it0
      //   prev_point[p] = it0->second;
      //   m[p.y] = p;
      // } else {
      //   // use it1
      //   prev_point[p] = it1->second;
      //   m[p.y] = p;
      // }
      // cerr << prev_point[p] << " ----> " << p << endl;
    };

    for (const auto& [x, type, y1, y2] : events) {
      // cerr << format("x: {}, type: {}, y = [{}, {}]", x, type, y1, y2) << endl;
      // cerr << "type: " << type << endl;

      // TODO: I'm not using the `type` lol
      if (type == -1) {
        update(x, y1);
      } else {
        update(x, y1);
        update(x, y2);
      }

      // TODO: I think I have to remove the items between y1 and y2???????
      while (true) {
        const auto it = m.lower_bound(y1 + 1);
        if (y2 - 1 <= it->first) break;
        m.erase(it);
      }

      // cerr << "curr map content:" << endl;
      // for (const auto& [y, p] : m) {
      //   if (y == INT_MIN || y == INT_MAX) continue;
      //   cerr << "    " << y << " : " << p << endl;
      // }
    }

    vector<Point> path;

    Point curr = dest;

    while (!(curr.x == 0 && curr.y == 0)) {
      path.emplace_back(curr);
      if (!prev_point.count(curr)) {
        cerr << "not found!!!!!!!!!!!!!!! prev of : " << curr << endl;
        // assert(false);
        break;
      }
      // assert(prev_point.count(curr));
      if (curr == prev_point[curr]) {
        cerr << "equal!!!!!!!!!!!!!! " << curr << endl;
        // assert(false);
        break;
      }
      curr = prev_point[curr];
    }

    path.emplace_back(curr);

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

    vector<Point> fixed_path;
    for (size_t i = 0; i < path.size() - 1; i++) {
      fixed_path.emplace_back(path[i]);
      if (path[i].x < path[i + 1].x) {
        fixed_path.emplace_back(path[i + 1].x, path[i].y);
      }
    }
    fixed_path.emplace_back(path.back());

    int total_len = 0;
    for (size_t i = 0; i < path.size() - 1; i++) {
      total_len += path[i].dist(path[i + 1]);
    }

    int another = 0;
    for (size_t i = 0; i < fixed_path.size() - 1; i++) {
      const Point p = fixed_path[i];
      const Point q = fixed_path[i + 1];
      another += p.dist(q);
      cerr << Segment{p, q}.to_desmos() << endl;
    }
    assert(total_len == another);

    cout << total_len << endl;
  }
}

• Subtask 1: 0 / 100