43 2021. 01. 08 20:34:38 mraron Chess Rush cpp11 Elfogadva 100/100 648ms 18204 KiB
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class bigint {
public:
    bigint(int v = 0);

    bigint &operator=(int v);
    friend bigint operator-(bigint v);

    friend bigint operator+(bigint a, const bigint &b);
    friend bigint operator-(bigint a, const bigint &b);
    bigint operator*(const bigint &v) const;
    bigint operator/(const bigint &v) const;
    
    bigint &operator+=(const bigint &other);
    bigint &operator-=(const bigint &other);
    bigint &operator*=(const bigint &v);
    bigint &operator/=(const bigint &v);

    friend std::istream &operator>>(std::istream &stream, bigint &v);
    friend std::ostream &operator<<(std::ostream &stream, const bigint &v);

private:
    int chkval;
};

void print_answer(const bigint& number_of_steps, const bigint& number_of_ways);


constexpr int P = 1e9+7;

bigint::bigint(int v) { *this = v; }

bigint& bigint::operator=(int v) {
    chkval = ((v % P) + P) % P;
    return *this;
}

bigint& bigint::operator+=(const bigint &other) {
    chkval += other.chkval;
    chkval %= P;
    return *this;
}

bigint operator+(bigint a, const bigint &b) {
    a.chkval += b.chkval;
    a.chkval %= P;
    return a;
}

bigint& bigint::operator-=(const bigint &other) {
    chkval += P - other.chkval;
    chkval %= P;
    return *this;
}

bigint operator-(bigint a, const bigint &b) {
    a.chkval += P - b.chkval;
    a.chkval %= P;
    return a;
}

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);
}

bigint bigint::operator/(const bigint &v) const { 
    bigint ret;
    ret.chkval = (1ll*chkval * modinv(v.chkval)) % P;
    return ret;
}

bigint& bigint::operator*=(const bigint &v) {
    chkval = (1ll*chkval * v.chkval) % P;
    return *this;
}

bigint& bigint::operator/=(const bigint &v) {
    *this = *this / v;
    return *this;
}

bigint operator-(bigint v) {
    if (v.chkval) v.chkval = P - v.chkval;
    return v;
}

istream &operator>>(istream &stream, bigint &v) {
    stream >> v.chkval;
    return stream;
}
ostream &operator<<(ostream &stream, const bigint &v) {
    stream << v.chkval;
    return stream;
}

bigint bigint::operator*(const bigint &v) const {
    bigint res;
    res.chkval = (1ll*chkval * v.chkval) % P;
    return res;
}

void print_answer(const bigint& number_of_steps, const bigint& number_of_ways) {
    cout << number_of_steps << " " << number_of_ways << endl;
}

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

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

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

pair<int,bigint> bounce_bishop(int s, int f, int r, int c) {
    pair<int,bigint> 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;
}

bigint DPup[maxc][maxc], newDP[maxc][maxc];
vector<bigint> DPright;
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] += DPup[s][c];
        newDP[s][c] += DPup[s][c];
        if (c+1<C) 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] += 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] = newDP[s-e][0] + newDP[s+1][e-1];
            else newDP[s][e] = 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();
    }

    if (R<C) {
        DPright = vector<bigint>(C,0);
        vector<bigint> DP(R,0); DP[R-1]=1;
        for (int c=1; c<C; ++c) {
            vector<bigint> newDP(R,0);
            for (int r=0; r<R; ++r) {
                if (r>0) newDP[r-1] += DP[r];
                newDP[r] += DP[r];
                if (r+1<R) newDP[r+1] += DP[r];
            }
            DP = newDP;
            DPright[c] = DP[0];
        }
    }
}

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,bigint> 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, leftans.second+rightans.second};
}
pair<int,bigint> kingsolve() {
    if (finish-start <= R-1) return {R-1, DPup[start-1][finish-1]};
    return {finish-start, DPright[finish-start]};
}

void solve() {
    cin >> piece >> start >> finish;
    if (finish<start) start=C+1-start, finish=C+1-finish;
    pair<int,bigint> 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 8ms 17788 KiB
2 Elfogadva 268ms 17860 KiB
subtask2 8/8
3 Elfogadva 8ms 17776 KiB
4 Elfogadva 10ms 17856 KiB
5 Elfogadva 8ms 17800 KiB
6 Elfogadva 29ms 17896 KiB
subtask3 15/15
7 Elfogadva 8ms 17816 KiB
8 Elfogadva 8ms 17900 KiB
9 Elfogadva 8ms 17820 KiB
10 Elfogadva 8ms 17880 KiB
subtask4 22/22
11 Elfogadva 207ms 17924 KiB
12 Elfogadva 79ms 17932 KiB
13 Elfogadva 9ms 17816 KiB
14 Elfogadva 540ms 17952 KiB
15 Elfogadva 9ms 17880 KiB
16 Elfogadva 13ms 17928 KiB
subtask5 5/5
17 Elfogadva 8ms 17936 KiB
18 Elfogadva 8ms 17896 KiB
19 Elfogadva 8ms 17900 KiB
20 Elfogadva 8ms 17856 KiB
subtask6 8/8
21 Elfogadva 9ms 17920 KiB
22 Elfogadva 9ms 18008 KiB
23 Elfogadva 10ms 18024 KiB
24 Elfogadva 12ms 17944 KiB
subtask7 15/15
25 Elfogadva 10ms 18016 KiB
26 Elfogadva 9ms 18040 KiB
27 Elfogadva 14ms 18072 KiB
28 Elfogadva 14ms 17992 KiB
29 Elfogadva 9ms 18100 KiB
30 Elfogadva 8ms 18004 KiB
subtask8 20/20
31 Elfogadva 9ms 18104 KiB
32 Elfogadva 10ms 18108 KiB
33 Elfogadva 546ms 18112 KiB
34 Elfogadva 620ms 18132 KiB
35 Elfogadva 469ms 18148 KiB
36 Elfogadva 504ms 18148 KiB
subtask9 7/7
37 Elfogadva 589ms 18168 KiB
38 Elfogadva 648ms 18184 KiB
39 Elfogadva 616ms 18188 KiB
40 Elfogadva 8ms 18200 KiB
41 Elfogadva 538ms 18204 KiB
42 Elfogadva 9ms 18136 KiB