Submission #416963

#	Time	Username	Problem	Language	Result	Execution time	Memory
416963		ACmachine	Chess Rush (CEOI20_chessrush)	C++17	51 / 100	2027 ms	262148 KiB

chessrush

#include "arithmetics.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i,j , k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
const int mx = 102;
const int mod = (int)1e9 + 7;
const int INF = (int)1e9 + 19;
struct matrix{
    ll mat[mx][mx];
    matrix(){
        REP(i, mx){
            fill(mat[i], mat[i] + mx, 0);
        }
    }
    matrix(vector<vector<int>> &a){
        REP(i, mx){
            fill(mat[i], mat[i] + mx, 0);
        }
        REP(i, a.size()){
            REP(j, a[i].size()){
                mat[i][j] = a[i][j];
            }
        }
    }
};
matrix multiply(matrix a, matrix b){
    matrix res;
    REP(i, mx){
        REP(j, mx){
            REP(k, mx){
                res.mat[i][k] = Add(res.mat[i][k], Mul(a.mat[i][j], b.mat[j][k]));
                //res.mat[i][k] += (a.mat[i][j] * b.mat[j][k]);
                //res.mat[i][k] %= mod;
            }
        }
    }
    return res;
};
matrix binpow(matrix a, int p){
    matrix res;
    REP(i, mx){
        res.mat[i][i] = 1;
    }
    while(p > 0){
        if(p & 1){
            res = multiply(res, a);
        }
        a = multiply(a, a);
        p >>= 1;
    }
    return res;
}
int main(){
    int r, c, q;
    cin >> r >> c >> q;
    auto solve_pawn = [&](int c1, int cr)->array<int,2>{
        if(c1 != cr) 
            return {0, 0};
        else{
            return {r - 1, 1};
        }
    };
    auto solve_queen = [&](int c1, int cr)->array<int,2>{
        if(c1 == cr){
            return {1, 1};
        }
        else if(abs(c1 - cr) == r - 1){
            return {1, 1};
        }
        else{
            array<int, 2> res = {2, 4};
            int f = r - 1 + cr - c1; int xf = f / 2;
            if(f % 2 == 0 && c1 + xf <= c && r - 1 - xf >= 0)
                res[1]++;
            int s = r - 1 + c1 - cr; int xs = s / 2;
            if(s % 2 == 0 && c1 - xs >= 1 && r - 1 - xs >= 0)
                res[1]++;
            if(r == c && (c1 == 1 || c1 == c)) 
                res[1]++;
            if(r == c && (cr == 1 || cr == c))
                res[1]++; 
            return res;
        }
    };
    auto solve_rook = [&](int c1, int cr)->array<int,2>{
        if(c1 == cr){
            return {1, 1};
        }
        else{
            return {2, 2};
        }
    };
    matrix kingpow;
    if(c < 101){
        matrix king;
        FOR(i, 1, c + 1, 1){
            if(i != c)
                king.mat[i][i + 1] = 1;
            king.mat[i][i] = 1;
            if(i != 1)
                king.mat[i][i - 1] = 1;
        }
        kingpow = binpow(king, r - 1);
    }
    auto solve_king = [&](int c1, int cr)->array<int, 2>{
        return {r - 1, kingpow.mat[c1][cr]};
    };
    auto solve_bishop = [&](int cr){
        vector<vector<array<int, 2>>> dp; 
        array<int, 2> nl = {INF, 0};
        dp.resize(r + 1, vector<array<int, 2>>(c + 1, nl));
        dp[r][cr] = {0, 1};
        FORD(i, r - 1, 1, 1){
            FOR(j, 1, c + 1, 1){
                int row = i;
                int col = j;
                REP(x, mx){
                    row++;
                    col--;
                    if(col < 1 || row > r) break;
                    if(dp[row][col][0] + 1 < dp[i][j][0]){
                        dp[i][j][0] = dp[row][col][0] + 1; 
                        dp[i][j][1] = dp[row][col][1];
                    }
                    else if(dp[row][col][0] + 1 == dp[i][j][0]){
                        dp[i][j][1] = Add(dp[i][j][1], dp[row][col][1]);
                    }
                }
                row = i;
                col = j;
                REP(x, mx){
                    row++;
                    col++;
                    if(col > c || row > r) break;
                    if(dp[row][col][0] + 1 < dp[i][j][0]){
                        dp[i][j][0] = dp[row][col][0] + 1; 
                        dp[i][j][1] = dp[row][col][1];
                    }
                    else if(dp[row][col][0] + 1 == dp[i][j][0]){
                        dp[i][j][1] = Add(dp[i][j][1], dp[row][col][1]);
                    }
                }
            }
        }
        return dp;
    };
    bool prepared = false;
    vector<vector<vector<array<int, 2>>>> bishop_grids;
    auto prepare_bishops = [&](){
        prepared = true;
        FOR(j, 1, c + 1, 1){
            bishop_grids.push_back(solve_bishop(j));
        }
    };
    auto solve_bishopp = [&](int c1, int cr)->array<int, 2>{
        if(!prepared){
            prepare_bishops();
        }
        array<int, 2> res = bishop_grids[cr - 1][1][c1];
        if(res[0] >= INF){
            return {0, 0};
        }
        else{
            return res;
        }
    };
    REP(i, q){
        char t;
        int c1, cr;
        cin >> t >> c1 >> cr;
        array<int, 2> res;
        if(t == 'P')
            res = solve_pawn(c1, cr);
        else if(t == 'Q')
            res = solve_queen(c1, cr);
        else if(t == 'R')
            res = solve_rook(c1, cr);
        else if(t == 'K')
            res = solve_king(c1, cr);
        else if(t == 'B')
            res = solve_bishopp(c1, cr);
        cout << res[0] << " " << res[1] << "\n";
    }
    return 0;
}

Compilation message (stderr)

chessrush.cpp: In constructor 'matrix::matrix(std::vector<std::vector<int> >&)':
chessrush.cpp:4:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
chessrush.cpp:6:19: note: in expansion of macro 'FOR'
    6 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
chessrush.cpp:23:9: note: in expansion of macro 'REP'
   23 |         REP(i, a.size()){
      |         ^~~
chessrush.cpp:4:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
chessrush.cpp:6:19: note: in expansion of macro 'FOR'
    6 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
chessrush.cpp:24:13: note: in expansion of macro 'REP'
   24 |             REP(j, a[i].size()){
      |             ^~~
chessrush.cpp: In lambda function:
chessrush.cpp:110:42: warning: narrowing conversion of 'kingpow.matrix::mat[c1][cr]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  110 |         return {r - 1, kingpow.mat[c1][cr]};
      |                        ~~~~~~~~~~~~~~~~~~^

• 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