#include <bits/stdc++.h>
#include "arithmetics.h"
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
int pow(int base, int exp) {
base %= MOD;
int result = 1;
while (exp > 0) {
if (exp & 1) result = (1ll * result * base) % MOD;
base = (1ll * base * base) % MOD;
exp >>= 1;
}
return result;
}
pair<int, int> solve_bishop(int x, int y, int r, int c) {
int moves = 1 + (r - x + c - 2) / (c - 1);
x--, y--;
int end_col = 1 + (r - x + c - 3) % (c - 1);
if (moves & 1) y = c - y - 1;
int rem;
if (end_col <= y)
rem = (y - end_col) / 2;
else {
moves++;
rem = c - 1 - (end_col + y) / 2;
}
int ways = 1;
for (int i = 1; i <= rem; i++)
ways = Div(Mul(ways, moves + rem - 1 - i), i);
return {moves, ways};
}
vector<vector<int>> precompute_king(int r, int c) {
vector<vector<int>> nxt(c + 2, vector<int>(c + 2, 0));
if (r == 2) {
for (int i = 1; i <= c; i++)
nxt[i][i - 1] = nxt[i][i] = nxt[i][i + 1] = 1;
for (int i = 1; i <= c; i++)
nxt[i][0] = nxt[i][c + 1] = nxt[0][i] = nxt[c + 1][i] = 0;
} else if (r & 1) {
vector<vector<int>> dp = precompute_king(r / 2 + 1, c);
for (int j = 1; j <= c; j++)
for (int k = 1; k <= c; k++) {
nxt[1][j] = Add(nxt[1][j], dp[1][k] * dp[k][j]);
nxt[j][1] = nxt[1][j];
}
for (int i = 2; i <= c; i++)
for (int j = 2; j <= c; j++)
if (i + j <= c + 1)
nxt[i][j] = Add(nxt[i - 1][j - 1], nxt[1][i + j - 1]);
for (int i = 2; i <= c; i++)
for (int j = 2; j <= c; j++)
if (i + j > c + 1)
nxt[i][j] = nxt[c + 1 - i][c + 1 - j];
} else {
vector<vector<int>> dp = precompute_king(r - 1, c);
for (int i = 1; i <= c; i++)
for (int j = 1; j <= c; j++)
nxt[i][j] = Add(dp[i][j - 1], Add(dp[i][j], dp[i][j + 1]));
}
return nxt;
}
int dp[1002][1002][2];
int main() {
cin.tie(0)->sync_with_stdio(0);
int r, c, q;
cin >> r >> c >> q;
vector<vector<int>> dp = precompute_king(r, c);
while (q--) {
char p;
int x, y;
cin >> p >> x >> y;
switch (p) {
case 'P':
if (x == y)
cout << r - 1 << " 1\n";
else
cout << "0 0\n";
break;
case 'R':
if (x == y)
cout << "1 1\n";
else
cout << "2 2\n";
break;
case 'Q':
if (x == y || x + r - 1 == y || x - r + 1 == y)
cout << "1 1\n";
else {
int ways = 4;
// Extremities
if (r == c && (y == 1 || y == r || x == 1 || x == r))
ways++;
if (x + y + r & 1) {
// Double diagonal
if (r - x < y) ways++;
if (r - c + x - 1 < c - y + 1) ways++;
}
cout << "2 " << ways << '\n';
}
break;
case 'B':
if (x + y + r & 1) {
if (r == c && ((x == 1 && y == c) || (x == c && y == 1)))
cout << "1 1\n";
else {
pair<int, int> move_left = solve_bishop(x, y, r, c);
pair<int, int> move_right =
solve_bishop(c - x + 1, c - y + 1, r, c);
if (move_left.first > move_right.first)
move_left = move_right;
else if (move_left.first == move_right.first) {
move_left.second = Add(move_left.second, move_right.second);
}
cout << move_left.first << ' ' << move_left.second
<< '\n';
}
} else
cout << "0 0\n";
break;
case 'K':
cout << r - 1 << ' ' << dp[x][y] << '\n';
break;
}
}
return 0;
}
Compilation message
chessrush.cpp: In function 'int main()':
chessrush.cpp:101:31: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
101 | if (x + y + r & 1) {
| ~~~~~~^~~
chessrush.cpp:110:27: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
110 | if (x + y + r & 1) {
| ~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
419 ms |
79124 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
288 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
35 ms |
7396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
412 ms |
67596 KB |
Output is correct |
| 6 |
Correct |
197 ms |
31336 KB |
Output is correct |
| 7 |
Correct |
6 ms |
520 KB |
Output is correct |
| 8 |
Correct |
1174 ms |
194356 KB |
Output is correct |
| 9 |
Correct |
2 ms |
332 KB |
Output is correct |
| 10 |
Correct |
15 ms |
1868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
419 ms |
79124 KB |
Output isn't correct |
