BOJ 20652 - Stuck in a Rut

BOJ 20652 - Stuck in a Rut

끔찍한 시뮬레이션 문제

$O(n^2)$ 에 <부딪히는 소, 부딪히는 시간, 위치, 나를 부딪히게 한 소> 같은 정보를 모두 모아두고 시간으로 오름차순 정렬한다.

이제 시간이 작은것부터 보면서 나를 부딪히게 한 소가 이 위치까지 도달할 수 있었는지에 대해 검사해주며 이 부딪힘이 유효한지를 검사해주며 각 소가 멈추는 위치를 결정할 수 있다.

struct Stop {
   int i, ex, ey, t, j = -1;

   bool operator<(const Stop &o) const {
      return t < o.t;
   }
};

void solve() {
   int n;
   cin >> n;
   vector<array<int, 3>> a;
   vector<pi> stop_at(n, {-1, -1});
   vector<Stop> stops;

   for (int i = 0; i < n; i++) {
      string d;
      int x, y;
      cin >> d >> x >> y;
      if (d == "N") {
         a.pb({0, x, y});
      } else {
         a.pb({1, x, y});
      }
   }
   debug(a);

   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (a[i][0] == 0 && a[j][0] == 0) {
            if (a[i][1] == a[j][1]) {
               if (a[i][2] > a[j][2]) stops.pb({j, a[i][1], a[i][2], a[i][2] - a[j][2], i});
               else stops.pb({i, a[j][1], a[j][2], a[j][2] - a[i][2], j});
            }
         } else if (a[i][0] == 1 && a[j][0] == 1) {
            if (a[i][2] == a[j][2]) {
               if (a[i][1] > a[j][1]) stops.pb({j, a[i][1], a[i][2], a[i][1] - a[j][1], i});
               else stops.pb({i, a[j][1], a[j][2], a[j][1] - a[i][1], j});
            }
         } else {
            int u = i, v = j;
            if (a[i][0] == 1) swap(u, v);
            if (a[u][2] > a[v][2]) continue;
            if (a[v][1] > a[u][1]) continue;

            int t = a[v][2] - a[u][2];
            int ex = a[u][1];
            int ey = a[u][2] + t;

            if (t == 0) {
               stops.pb({v, a[u][1], a[u][2], a[u][1] - a[v][1], u});
               continue;
            }

            int t_horizontal = a[u][1] - a[v][1];
            if(t_horizontal == 0) {
               stops.pb({u, a[v][1], a[v][2], a[v][2] - a[u][2], v});
               continue;
            }

            if (t_horizontal == t) continue;

            if (t_horizontal > t) {
               stops.pb({v, ex, ey, t_horizontal, u});
            } else {
               stops.pb({u, ex, ey, t, v});
            }
         }
      }
   }
   sort(all(stops));
   auto can_go = [&](int i, int x, int y) -> bool {
      if (stop_at[i].fi == -1) return true;
      if (a[i][0] == 0) {
         if (x != a[i][1]) return false;
         if (stop_at[i].se < y) return false;
      } else {
         if (y != a[i][2]) return false;
         if (stop_at[i].fi < x) return false;
      }
      return true;
   };
   for (int i = 0; i < sz(stops); i++) {
      Stop s = stops[i];
      // already stop
      if (stop_at[s.i].fi != -1) continue;
      if (!can_go(s.j, s.ex, s.ey)) continue;

      stop_at[s.i] = {s.ex, s.ey};
   }
   for (int i = 0; i < n; i++) {
      if (stop_at[i].fi == -1) cout << "Infinity\n";
      else cout << abs(a[i][1] - stop_at[i].fi) + abs(a[i][2] - stop_at[i].se) << endl;
   }
   debug(stop_at);
}