oj.uz

Submission #416963

# Submission time Handle Problem Language Result Execution time Memory
416963 2021-06-03T08:44:30 Z ACmachine Chess Rush (CEOI20_chessrush) C++17
51 / 100
 2000 ms 262148 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 716 KB Output is correct
2 Runtime error 119 ms 262148 KB Execution killed with signal 9

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 716 KB Output is correct
2 Correct 447 ms 752 KB Output is correct
3 Correct 54 ms 772 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 716 KB Output is correct
2 Correct 149 ms 884 KB Output is correct
3 Correct 134 ms 772 KB Output is correct
4 Correct 136 ms 900 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 716 KB Output is correct
2 Correct 149 ms 884 KB Output is correct
3 Correct 134 ms 772 KB Output is correct
4 Correct 136 ms 900 KB Output is correct
5 Execution timed out 2027 ms 24016 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 752 KB Output is correct
2 Correct 148 ms 748 KB Output is correct
3 Correct 133 ms 716 KB Output is correct
4 Correct 133 ms 748 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 752 KB Output is correct
2 Correct 148 ms 748 KB Output is correct
3 Correct 133 ms 716 KB Output is correct
4 Correct 133 ms 748 KB Output is correct
5 Correct 166 ms 768 KB Output is correct
6 Correct 138 ms 748 KB Output is correct
7 Correct 145 ms 748 KB Output is correct
8 Correct 150 ms 752 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 752 KB Output is correct
2 Correct 148 ms 748 KB Output is correct
3 Correct 133 ms 716 KB Output is correct
4 Correct 133 ms 748 KB Output is correct
5 Correct 166 ms 768 KB Output is correct
6 Correct 138 ms 748 KB Output is correct
7 Correct 145 ms 748 KB Output is correct
8 Correct 150 ms 752 KB Output is correct
9 Correct 417 ms 756 KB Output is correct
10 Correct 771 ms 748 KB Output is correct
11 Correct 764 ms 772 KB Output is correct
12 Correct 694 ms 760 KB Output is correct
13 Correct 566 ms 748 KB Output is correct
14 Correct 610 ms 768 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 752 KB Output is correct
2 Correct 148 ms 748 KB Output is correct
3 Correct 133 ms 716 KB Output is correct
4 Correct 133 ms 748 KB Output is correct
5 Correct 166 ms 768 KB Output is correct
6 Correct 138 ms 748 KB Output is correct
7 Correct 145 ms 748 KB Output is correct
8 Correct 150 ms 752 KB Output is correct
9 Correct 417 ms 756 KB Output is correct
10 Correct 771 ms 748 KB Output is correct
11 Correct 764 ms 772 KB Output is correct
12 Correct 694 ms 760 KB Output is correct
13 Correct 566 ms 748 KB Output is correct
14 Correct 610 ms 768 KB Output is correct
15 Correct 642 ms 752 KB Output is correct
16 Correct 615 ms 764 KB Output is correct
17 Runtime error 1 ms 716 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 716 KB Output is correct
2 Runtime error 119 ms 262148 KB Execution killed with signal 9