Submission #1231082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231082		The_Samurai	Chess Rush (CEOI20_chessrush)	C++20	51 / 100	2096 ms	4928 KiB

chessrush

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

constexpr int mod = 1e9+7;
int binpow(int base, int exp, int modulus=mod) {
    base %= modulus;
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = (1ll*result * base) % modulus;
        base = (1ll*base * base) % modulus;
        exp >>= 1;
    }
    return result;
}


int n, m, q;
vector<vector<int>> merge(const vector<vector<int>> &a, const vector<vector<int>> &b) {
    vector ans(m, vector(m, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
                // ans[i][k] += a[i][j] * b[j][k];
                ans[i][k] = (ans[i][k] + ll(a[i][j]) * b[j][k]) % mod;
            }
        }
    }
    return ans;
}

bool bish(int x1, int y1, int x2, int y2) {
    return x1 + y1 == x2 + y2 or x1 - y1 == x2 - y2;
}

int main() {
    cin >> n >> m >> q;
    int lg = 0;
    while ((1 << lg) < n) lg++;
    vector<vector<vector<int>>> dp;
    vector ans(m, vector(m, 0));
    if (m <= 100) {
        dp = vector(lg, vector(m, vector(m, 0)));
        for (int i = 0; i < m; i++) {
            dp[0][i][i] = 1;
            if (i > 0) dp[0][i][i - 1] = 1;
            if (i + 1 < m) dp[0][i][i + 1] = 1;
        }
        for (int i = 1; i < lg; i++) dp[i] = merge(dp[i - 1], dp[i - 1]);
        bool emp = true;
        for (int i = lg - 1; i >= 0; i--) {
            if ((n - 1) >> i & 1) {
                if (emp) ans = dp[i];
                else ans = merge(ans, dp[i]);
                emp = false;
            }
        }
    }

    auto upd = [&](pair<int, int> &a, pair<int, int> b) {
        if (a.first > b.first) a = make_pair(b.first, 0);
        if (a.first == b.first) a.second = (a.second + b.second) % mod;
    };

    while (q--) {
        char op;
        int c1, c2;
        cin >> op >> c1 >> c2;
        if (op == 'P') {
            if (c1 == c2) cout << n - 1 << " 1\n";
            else cout << "0 0\n";
        } else if (op == 'R') {
            if (c1 == c2) cout << "1 1\n";
            else cout << "2 2\n";
        } else if (op == 'Q') {
            if (c1 == c2 or bish(c1, 1, c2, n)) cout << "1 1\n";
            else {
                cout << "2 ";
                set<pair<int, int>> st;
                st.emplace(1, c2);
                st.emplace(n, c1);
                int x = 1, y = c1;
                for (int i = 1; i <= m; i++) {
                    if (x + i > n) continue;
                    if (y - i > 0) {
                        if (bish(x + i, y - i, n, c2) or x + i == n or y - i == c2) st.emplace(x + i, y - i);
                    }
                    if (y + i <= m) {
                        if (bish(x + i, y + i, n, c2) or x + i == n or y + i == c2) st.emplace(x + i, y + i);
                    }
                }
                x = n, y = c2;
                for (int i = 1; i <= m; i++) {
                    if (x - i <= 0) continue;
                    if (y - i > 0) {
                        if (bish(x - i, y - i, 1, c1) or x - i == 1 or y - i == c1) st.emplace(x - i, y - i);
                    }
                    if (y + i <= m) {
                        if (bish(x - i, y + i, 1, c1) or x - i == 1 or y + i == c1) st.emplace(x - i, y + i);
                    }
                }
                cout << st.size() << '\n';
            }
        } else if (op == 'K') {
            cout << n - 1 << ' ' << ans[c1 - 1][c2 - 1] << '\n';
        } else if (op == 'B') {
            if ((1 + c1) % 2 != (n + c2) % 2) {
                cout << "0 0\n";
                continue;
            }
            queue<pair<int, int>> q;
            map<int, pair<int, int>> left, right;
            for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) {
                left[x + y] = right[x - y] = make_pair(2e9, 0);
            }
            for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) {
                pair<int, int> now = make_pair(2e9, 0);
                upd(now, left[x + y]);
                upd(now, right[x - y]);
                if (x == 1 and y == c1) now = make_pair(0, 1);
                if (x == n and y == c2) {
                    cout << now.first << ' ' << now.second << '\n';
                    break;
                }
                now.first++;
                upd(left[x + y], now);
                upd(right[x - y], now);
            }
        }
    }
}

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 0 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7