Submission #1326383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326383		shirokuma5	Chess Rush (CEOI20_chessrush)	C++20	28 / 100	2100 ms	327680 KiB

chessrush

//# pragma GCC target("avx2")
//# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include "arithmetics.h"
using ll = long long;
using namespace std;
const ll mod = 998244353;
const ll INF = 1LL << 60;
const int MAX = 1e9 + 10;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); i++)
#define repd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repd1(i, n) for (int i = (int)(n); i >= 1; i--)
#define repd2(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); i--)

/*constexpr int P = 1e9+7;

int Add(int a, int b) {
	int ret = a%P;
	ret = (ret<0 ? P+ret : ret) + (b%P);
	return (ret>=0 ? ret%P : ret+P);
}

int Sub(int a, int b) {
	int ret = a%P;
	ret = (ret<0 ? P+ret : ret) - (b%P);
	return (ret>=0 ? ret%P : ret+P);
}

int Mul(int a, int b) {
	int ret = (1ll*(a%P) * (b%P)) % P;
	return (ret<0 ? P+ret : ret);
}

int modpow(int base, int exp, int modulus=P) {
  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 modinv(int a, int modulus=P) {
  return modpow(a,modulus-2);
}

int Div(int a, int b) {
	int ret = b%P;
	ret = (1ll*(a%P) * modinv(ret<0 ? P+ret : ret)) % P;
	return (ret<0 ? P+ret : ret);
}*/

template<class T> bool chmin(T &a, T b) {
    if (a > b) {
        a = b; return 1;
    }
    return 0;
}
template<class T> bool chmax(T &a, T b) {
    if (a < b) {
        a = b; return 1;
    }
    return 0;
}
struct edge {
    int to, w;
};
ll inv(ll a) {
    ll b = mod, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= b * t;
        swap(a, b);
        u -= v * t;
        swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}
template<class T> void print(vector<T> a) {
    int n = a.size();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
}
template<class T> int low_idx(const vector<T> &a, T x) {
    return distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
template<class T> bool next_combination(T &bit, int N) {
    T x = bit & -bit, y = bit + x;
    bit = (((bit & ~y) / x) >> 1) | y;
    return (bit < (1LL << N));
}
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

using v2 = vector<vector<int>>;
v2 seki(const v2 &a, const v2 &b) {
    int k = a.size(), l = b[0].size(), m = b.size();
    assert(a[0].size() == m);
    v2 ret(k, vector<int> (l, 0));
    rep(i, k) rep(j, l) rep(ix, m) ret[i][j] = Add(ret[i][j], Mul(a[i][ix], b[ix][j]));
    return ret;
}

int Cmax;
vector<v2> po;
v2 rui(int x) {
    v2 ret(Cmax, vector<int> (Cmax, 0));
    rep(i, Cmax) ret[i][i] = 1;
    rep(i, 30) if ((x >> i) & 1) ret = seki(ret, po[i]);
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int R, C, Q; cin >> R >> C >> Q; Cmax = C;
    po.assign(30, v2(Cmax, vector<int> (Cmax, 0)));
    rep(i, Cmax) rep(j, Cmax) if (abs(i-j) <= 1) po[0][i][j] = 1;
    rep1(i, 29) po[i] = seki(po[i-1], po[i-1]);
    v2 rr = rui(R-1);

    vector<vector<vector<pair<int, int>>>> bi(min(C,100), 
        vector<vector<pair<int, int>>> (R, vector<pair<int, int>> (min(C,100), {MAX, 0})));
    int mini = min(C,100);
    rep(i, mini) {
        bi[i][0][i] = {0, 1};
        rep(j, R-1) rep(k, mini) {
            if (bi[i][j][k].first == MAX) continue;
            for (int l = 1; j + l < R; l++) {
                if (k - l >= 0) {
                    if (chmin(bi[i][j+l][k-l].first, bi[i][j][k].first+1)) bi[i][j+l][k-l].second = bi[i][j][k].second;
                    else if (bi[i][j+l][k-l].first > bi[i][j][k].first) bi[i][j+l][k-l].second = Add(bi[i][j+l][k-l].second, bi[i][j][k].second);
                }
                else break;
            }
            for (int l = 1; j + l < R; l++) {
                if (k+l < mini) {
                    if (chmin(bi[i][j+l][k+l].first, bi[i][j][k].first+1)) bi[i][j+l][k+l].second = bi[i][j][k].second;
                    else if (bi[i][j+l][k+l].first > bi[i][j][k].first) bi[i][j+l][k+l].second = Add(bi[i][j+l][k+l].second, bi[i][j][k].second);
                }
                else break;
            }
        }
    }
    /*rep(i, R) {
        rep(j, C) cerr << "{" << bi[4][i][j].first << "," << bi[4][i][j].second << "}";
        cerr << endl;
    }
    cerr << endl;*/

    while (Q--) {
        char ch; int x, y; cin >> ch >> x >> y;
        if (x > y) swap(x, y);
        if (ch == 'P') {
            if (x == y) cout << R - 1 << " " << 1 << endl;
            else cout << "0 0\n";
            continue;
        }
        if (ch == 'R') {
            if (x == y) cout << "1 1\n";
            else cout << "2 2\n";
            continue;
        }
        if (ch == 'Q') {
            if (x == y) cout << "1 1\n";
            else if (x + R - 1 == y || y + R - 1 == x) cout << "1 1\n";
            else {
                int res = 4;
                if ((R + y - x - 1) % 2 == 0) {
                    int a = ((1+x)+(R-y))/2, b = ((1+x)-(R-y))/2;
                    if (1 < a && a < R && 1 <= b && b <= C) res++;
                    a = ((1-x)+(R+y))/2, b = ((R+y)-(1-x))/2;
                    if (1 < a && a < R && 1 <= b && b <= C) res++;
                }
                if (R == C && ((x == 1 && y < C) || (y == C && x > 1))) res++;
                cout << "2 " << res << endl;
            }
            continue;
        }
        if (ch == 'K') {
            v2 v(C, vector<int> (1, 0)); v[x-1][0] = 1;
            v = seki(rr, v);
            cout << R-1 << " " << v[y-1][0] << endl; continue;
        }
        if (ch == 'B') {
            if ((R - 1 + x + y) % 2 == 1) {
                cout << "0 0\n"; continue;
            }
            if (C <= 100 && R <= 100) {
                cout << bi[x-1][R-1][y-1].first << " " << bi[x-1][R-1][y-1].second << endl; continue;
            }
        }
    }
}

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