Editorial for Bedao Grand Contest 16 - FROG


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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:

image

~\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}~:

image

Ta sẽ xoay trục toạ độ ~-90^{\circ}~:

image

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:

image

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~:

image

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.

Code mẫu

#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

Please read the guidelines before commenting.


There are no comments at the moment.