Editorial for Bedao Grand Contest 16 - FROG
Submitting an official solution before solving the problem yourself is a bannable offence.
Ở subtask ~1~, ta có thể dễ dàng làm trong ~O~(~qm~) với công thức xoay góc:
~\texttt{cw}~ thì ta xoay góc ~-90^{\circ}~ còn ~\texttt{ccw}~ thì ta xoay góc ~90^{\circ}~.
Ở subtask ~2~, ta để ý là xét ~1~ con ếch, nếu chỉ thực hiện xoay, chỉ có ~4~ khả năng vị trị nó xoay đến thôi, tương ứng khi xoay ~0^{\circ}~, ~90^{\circ}~, ~180^{\circ}~, ~270^{\circ}~. Nên với mỗi con ếch, ta lưu lại tổng số góc nó được xoay, xong tiến hành xoay để trả lời truy vấn.
Ở subtask ~3~, ta có nhận xét thứ nhất là ~\texttt{xflip}~ và ~\texttt{yflip}~ độc lập với nhau, hay không ảnh hưởng gì đến nhau, nên ta có thể chia riêng để giải quyết và cách giải quyết cũng tương tự nhau.
Giờ ta cần giải quyết ~\texttt{xflip}~, để ý rằng toạ độ ~x~ khi thực hiện ~\texttt{xflip}~ ~k~ là:
~x' = x + 2 \times (k - x) = x + 2 \times k - 2 \times x = 2 \times k - x~
nếu thực hiện tiếp ~\texttt{xflip}~ ~k'~ thì toạ độ ~x'~ sau đó là:
~x'' = x' + 2 \times (k' - x') = 2 \times k' - x' = 2 \times k' - 2 \times k + x~
tiếp tục ~\texttt{xflip}~ ~k''~, toạ độ sẽ là:
~2 \times k'' - 2 \times k' + 2 \times k - x~
Nhìn vào thì ta nhận ra rằng phần tổng hiệu của các ~k~ ở trước ~x~ ta có thể dễ dàng duy trì được: gọi là ~sumK~, sau mỗi lần ~\texttt{xflip}~ ~k~, ~sumK = 2 \times k - sumK~ .Còn dấu của ~x~, với ~x~ là hoành độ ban đầu, tuỳ thuộc số lần ~\texttt{xflip}~, thực hiện lẻ lần sẽ là ~-~, chẵn là ~+~, cộng thêm ~sumK~ sẽ ra toạ độ ~x~.
Ở subtask cuối cùng, ta sẽ kết hợp lại cách giải quyết của ~2~ subtask trước để thực hiện. Để dễ hình dung thì ta sẽ xoay bằng cách khác. Thay vì trước kia, ta xoay trực tiếp con ếch thì giờ ta sẽ giữ nguyên ếch nhưng lại xoay hệ trục toạ độ, rồi tính lại vị trí ếch. Ví dụ, ta xoay điểm (~4, 5~) ~90^{\circ}~:
Ta sẽ xoay trục toạ độ ~-90^{\circ}~:
Thì điểm (~4, 5~) gốc ở trục toạ độ sau khi xoay sẽ ở đúng vị trí của điểm (~-5, 4~) mà mình cần xoay tới ở trục toạ độ ban đầu:
Ta thực hiện như thế này bởi vì cách tính ~\texttt{flip}~ của ta dựa trên toạ độ ban đầu trên hệ trục toạ độ gốc, và nhận xét thêm rằng ta chỉ cần thay đổi đường thẳng ~\texttt{flip}~ tương ứng và thực hiện y chang subtask ~3~, ví dụ ~\texttt{xflip}~ ~3~:
Ta cần ~\texttt{xflip}~ qua đường thẳng ~x = 3~ nhưng vì đã xoay hệ trục toạ độ nên đường thẳng đó sẽ là đường thẳng ~y = -3~ tương ứng trong hệ trục toạ độ gốc, đồng nghĩa với việc ta cần phải thực hiện ~\texttt{yflip}~ ~-3~ y như subtask ~3~.
Tóm lại, ở subtask này, ta cần phải lưu lại số góc xoay của hệ trục toạ độ để xoay đường thẳng ~\texttt{flip}~ tương ứng. Để trả lời truy vấn, ta phải tính ra toạ độ của ếch sau khi flip, và dựa trên số góc xoay của hệ trục toạ độ để xoay toạ độ phù hợp.
Độ phức tạp cho ~3~ subtask cuối đều là ~O~(~qlogq~) bởi vì ta cần sắp xếp lại các truy vấn theo thứ tự thực hiện thao tác, để vừa thực hiện thao tác vừa trả lời song song.
#include <bits/stdc++.h> using namespace std; template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;} template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;} #define all(a) a.begin(), a.end() #define pb push_back #define pf push_front #define fi first #define se second #define int long long typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; typedef pair<db, db> pdb; typedef pair<ld, ld> pld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ll, int> plli; typedef pair<int, ll> pill; const int MAX_N = 2e5 + 5; int numPoint, numEvent, numQ; pii a[MAX_N]; pair<string, int> event[MAX_N]; pair<pii, int> q[MAX_N]; pii ans[MAX_N]; bool cntFlipX, cntFlipY; int valFlipX, valFlipY; void addFlipX(const int& K) { cntFlipX ^= 1; valFlipX = (K << 1) - valFlipX; } void addFlipY(const int& K) { cntFlipY ^= 1; valFlipY = (K << 1) - valFlipY; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> numPoint >> numEvent >> numQ; for (int i = 1; i <= numPoint; i++) { cin >> a[i].fi >> a[i].se; } for (int i = 1; i <= numEvent; i++) { cin >> event[i].fi; if (event[i].fi[0] != 'c') { cin >> event[i].se; } } for (int i = 1; i <= numQ; i++) { cin >> q[i].fi.se >> q[i].fi.fi; // b a q[i].se = i; } sort(q + 1, q + numQ + 1); int j = 1, spinTurn = 0; for (int i = 1; i <= numQ; i++) { while (j <= q[i].fi.fi) { if (event[j].fi[0] == 'c') { if (event[j].fi[1] == 'w') { spinTurn++; if (spinTurn == 4) spinTurn = 0; } else { spinTurn--; if (spinTurn < 0) spinTurn = 3; } j++; continue; } int k = event[j].se; if (event[j].fi[0] == 'x') { if (spinTurn & 1) { addFlipY(k * (spinTurn > 1 ? -1 : 1)); } else { addFlipX(k * (spinTurn > 1 ? -1 : 1)); } } else { if (spinTurn & 1) { addFlipX(k * (spinTurn == 1 ? -1 : 1)); } else { addFlipY(k * (spinTurn == 2 ? -1 : 1)); } } j++; } pii curr = a[q[i].fi.se]; curr.fi = valFlipX + (cntFlipX ? -1 : 1) * curr.fi; curr.se = valFlipY + (cntFlipY ? -1 : 1) * curr.se; for (int time = 1; time <= spinTurn; time++) { curr = {curr.se, -curr.fi}; } ans[q[i].se] = curr; } for (int i = 1; i <= numQ; i++) { cout << ans[i].fi << ' ' << ans[i].se << '\n'; } return 0; } /* Monday, 08 April 2024 21:59:01 */
Comments