#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 = 1020;
const int mod = (int)1e9 + 7;
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 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;
}
matrix kingpow = binpow(king, r - 1);
auto solve_king = [&](int c1, int cr)->array<int, 2>{
return {r - 1, kingpow.mat[c1][cr]};
};
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);
cout << res[0] << " " << res[1] << "\n";
}
return 0;
}
Compilation message
chessrush.cpp: In constructor 'matrix::matrix(std::vector<std::vector<int> >&)':
chessrush.cpp:5:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
chessrush.cpp:7:19: note: in expansion of macro 'FOR'
7 | #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:5:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
chessrush.cpp:7:19: note: in expansion of macro 'FOR'
7 | #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:107:42: warning: narrowing conversion of 'kingpow.matrix::mat[c1][cr]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
107 | return {r - 1, kingpow.mat[c1][cr]};
| ~~~~~~~~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2050 ms |
49100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2070 ms |
49136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2067 ms |
49100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2067 ms |
49100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
49088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
49088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
49088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
49088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2050 ms |
49100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
