BOJ 28300 - 응원단

image.png

$4$개의 칸만 어디로 이동이 되는지 각 쿼리마다 체크하면 되는 것을 관찰한다.

$S$ 연산에서는 $S$ 연산이 시행된 당시에 $r_1,c_1$ 이 그 네 개중 어디에 속하고 현재 그 그룹의 시작지점과 얼마나 $r,c$ 가 차이나는지 여부와 $r_2,c_2$ 도 같이 기록해둔다.

마지막에 모든 쿼리를 처리하고 $S$ 연산을 순차대로 시행하며 스왑을 그대로 해주면 된다.

void solve() {
   int n, q;
   cin >> n >> q;
   vector<pi> o = {
      {0, 0}, {0, 1}, {1, 0}, {1, 1},
   };

   vector<array<int, 6>> swap_history;
   while (q--) {
      string cmd;
      cin >> cmd;
      if (cmd == "RO") {
         for (int i = 0; i < 4; i++) {
            if (o[i].fi % 2 == 0)
               o[i].se = md(n, o[i].se + 1);
         }
      }
      if (cmd == "RE") {
         for (int i = 0; i < 4; i++) {
            if (o[i].fi % 2 == 1)
               o[i].se = md(n, o[i].se + 1);
         }
      }
      if (cmd == "CO") {
         for (int i = 0; i < 4; i++) {
            if (o[i].se % 2 == 0)
               o[i].fi = md(n, o[i].fi + 1);
         }
      }
      if (cmd == "CE") {
         for (int i = 0; i < 4; i++) {
            if (o[i].se % 2 == 1)
               o[i].fi = md(n, o[i].fi + 1);
         }
      }
      if (cmd == "S") {
         int y1, x1, y2, x2;
         cin >> y1 >> x1 >> y2 >> x2, y1--, x1--, y2--, x2--;

         int i1 = -1, i2 = -1;
         for (int i = 0; i < 4; i++) {
            if (abs(y1 - o[i].fi) % 2 == 0 && abs(x1 - o[i].se) % 2 == 0) {
               assert(i1 == -1);
               i1 = i;
            }
            if (abs(y2 - o[i].fi) % 2 == 0 && abs(x2 - o[i].se) % 2 == 0) {
               assert(i2 == -1);
               i2 = i;
            }
         }
         assert(i1 != -1 && i2 != -1);
         swap_history.pb({i1, y1 - o[i1].fi, x1 - o[i1].se, i2, y2 - o[i2].fi, x2 - o[i2].se});
      }
   }
   vvi ans(n, vi(n));
   debug(o);
   for (int i = 0; i < 4; i++) {
      int num = i == 0 ? 1 : i == 1 ? 2 : i == 2 ? n + 1 : n + 2;
      for (int y = o[i].fi, c = 0; c < n / 2; c++, y = md(n, y + 2)) {
         for (int x = o[i].se, c2 = 0; c2 < n / 2; c2++, x = md(n, x + 2), num += 2) {
            ans[y][x] = num;
         }
         num += n;
      }
   }
   for (auto &[i1, dy1, dx1, i2, dy2, dx2]: swap_history) {
      swap(ans[md(n, o[i1].fi + dy1)][md(n, o[i1].se + dx1)], ans[md(n, o[i2].fi + dy2)][md(n, o[i2].se + dx2)]);
   }
   for (int y = 0; y < n; y++) {
      for (int x = 0; x < n; x++) {
         cout << ans[y][x] << ' ';
      }
      cout << endl;
   }
}

Tags:

Categories:

Updated:

Comments