Submission #290101

#	Time	Username	Problem	Language	Result	Execution time	Memory
290101		model_code	Chess Rush (CEOI20_chessrush)	C++17	100 / 100	1034 ms	8312 KiB

chessrush

#include <iostream>
#include <algorithm>
#include <vector>

#include "arithmetics.h"

using namespace std;

int Q, R,C, start, finish;
char piece;

const int maxc=1010;
int fact[maxc];

void precalc() {
    fact[0] = 1;
    for (int i=1; i<maxc; ++i) {
        fact[i] = Mul(fact[i-1], i);
    }
}
int comb(int n, int k) {
    int ret = 1;
    for (int x=n-k+1; x<=n; ++x) {
        ret = Mul(ret, x);
    }
    return Div(ret, fact[k]);
}

pair<int,int> bounce_bishop(int s, int f, int r, int c) {
    pair<int,int> ret = { 0,0 };
    if (s!=1) {
        int wallrow = s;
        ret.first = 1+(r-wallrow)/(c-1);
        ret.second = 1;
        int remrow = (r-wallrow)%(c-1);
        bool fromleft=ret.first & 1;
        int impactfield = fromleft ? 1+remrow : c-remrow;
        if (remrow>0) ++ret.first;
        if (impactfield == f) return ret;
        if (remrow==0) ++ret.first;
        int freediag;
        if (fromleft) {
            if (f<impactfield) {
                freediag = c+1-(impactfield+f)/2-1;
                ++ret.first;
            }
            else {
                freediag = (f-impactfield)/2;
            }
        }
        else {
            if (f>impactfield) {
                freediag = (f+impactfield)/2-1;
                ++ret.first;
            }
            else {
                freediag = (impactfield-f)/2;
            }
        }
        ret.second = comb(ret.first-2+freediag,freediag);
    }
    return ret;
}

int DPup[maxc][maxc], newDP[maxc][maxc];
void onestep() {
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) newDP[s][c]=0;
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) {
        if (c>0) newDP[s][c-1] = Add(newDP[s][c-1], DPup[s][c]);
        newDP[s][c] = Add(newDP[s][c], DPup[s][c]);
        if (c+1<C) newDP[s][c+1] = Add(newDP[s][c+1], DPup[s][c]);
    }
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) DPup[s][c] = newDP[s][c];
}
void doublestep() {
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) newDP[s][c]=0;
    for (int s=0; s<C; ++s) {
        for (int mid=0; mid<C; ++mid) {
            newDP[s][0] = Add(newDP[s][0], Mul(DPup[s][mid],DPup[mid][0]));
        }
    }
    for (int e=1; e<C; ++e) newDP[0][e] = newDP[e][0], newDP[C-1][e] = newDP[C-1-e][0];
    for (int e=1; 2*e<C; ++e) {
        for (int s=1; s+1<C; ++s) {
            if (s-e>=0) newDP[s][e] = Add(newDP[s-e][0], newDP[s+1][e-1]);
            else newDP[s][e] = Add(newDP[s+e][0], newDP[s-1][e-1]);
        }
    }
    for (int e=(C-1)/2+1; e<C; ++e) {
        for (int s=1; s+1<C; ++s) {
            newDP[s][e] = newDP[C-1-s][C-1-e];
        }
    }
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) DPup[s][c] = newDP[s][c];
}
void kingDP() {
    for (int s=0; s<C; ++s) for (int c=0; c<C; ++c) DPup[s][c] = 0;
    for (int s=0; s<C; ++s) {
        DPup[s][s]=1;
    }
    vector<bool> steplist;
    int r=R-1;
    while (r>0) {
        steplist.push_back(r&1);
        r >>= 1;
    }
    while (!steplist.empty()) {
        if (steplist.back()) onestep();
        steplist.pop_back();
        if (steplist.size()>0) doublestep();
    }
}

pair<int,int> pawnsolve() {
    if (start==finish) return {R-1,1};
    return {0,0};
}
pair<int,int> rooksolve() {
    if (start==finish) return {1,1};
    return {2,2};
}
pair<int,int> queensolve() {
    if (start==finish || finish-start == R-1) return {1,1};
    pair<int,int> ret = {2,2};
    if (start>finish-R+1) ret.second+=2;
    if (start-R+1>0) ret.second++;
    if (finish-R+1>0) ret.second++;
    if (finish+R-1<=C) ret.second++;
    if (start+R-1<=C) ret.second++;
    if ((start+1)%2 == (R+finish)%2) {
        int k = (R+finish-start-1)/2;
        int l = R-k-1;
        if (k>0 && l>0 && start-l>0) ret.second++;
        if (k>0 && l>0 && start+k<=C) ret.second++;
    }
    return ret;
}
pair<int,int> bishopsolve() {
    if ((start+1)%2 != (R+finish)%2) return {0,0};
    if (start+R-1 == finish || start-R+1==finish) return {1,1};
    int r=R,c=C;
    if (finish-start+1 > R) r=finish-start+1, c=R, start=1, finish=R;
    int k = (r+finish-start-1)/2;
    int l = r-k-1;
    int cnt = (start-l>0) + (start+k<=c);
    if (k>0 && l>0 && cnt>0) return {2,cnt};
    auto leftans = bounce_bishop(start,finish,r,c);
    auto rightans = bounce_bishop(c+1-start,c+1-finish,r,c);
    if (leftans.first==0 || (rightans.first>0 && leftans.first>rightans.first)) return rightans;
    if (rightans.first==0 || rightans.first>leftans.first) return leftans;
    return {leftans.first, Add(leftans.second,rightans.second)};
}
pair<int,int> kingsolve() {
    return {R-1, DPup[start-1][finish-1]};
}

void solve() {
    cin >> piece >> start >> finish;
    if (finish<start) start=C+1-start, finish=C+1-finish;
    pair<int,int> ans;
    if (piece=='P') ans = pawnsolve();
    if (piece=='R') ans = rooksolve();
    if (piece=='Q') ans = queensolve();
    if (piece=='B') ans = bishopsolve();
    if (piece=='K') ans = kingsolve();
    cout << ans.first << " " << ans.second << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> R >> C >> Q;
    precalc();
    kingDP();
    while (Q--) solve();
    return 0;
}

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