#include <iostream>
#include "arithmetics.h"
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;
pair<int, int> pawn(int r, int c, int j0, int j1) {
if (j0 == j1)
return {r - 1, 1};
else
return {0, 0};
}
pair<int, int> rook(int r, int c, int j0, int j1) {
if (j0 == j1)
return {1, 1};
else
return {2, 2};
}
struct point {
ll x, y;
point(){}
point(ll x_, ll y_): x(x_), y(y_) {}
point operator/(ll t) const {
return {x / t, y / t};
}
point operator*(ll t) const {
return {x * t, y * t};
}
bool operator==(point pt) const {
return x == pt.x && y == pt.y;
}
bool operator!=(point pt) const {
return x != pt.x || y != pt.y;
}
ll operator*(point pt) const {
return x * pt.y - y * pt.x;
}
ll operator^(point pt) const {
return x * pt.x + y * pt.y;
}
point operator+(point pt) const {
return {x + pt.x, y + pt.y};
}
point operator-(point pt) const {
return {x - pt.x, y - pt.y};
}
point rotate_45_normal() {
point ans(x - y, x + y);
if (abs(x + y) == 2 || abs(x - y) == 2)
return ans / 2;
else
return ans;
}
point rotate_90() {
return {-y, x};
}
};
pair<int, int> queen(int r, int c, int j0, int j1) {
for (point dir(1, 0); dir != point(-1, 0); dir = dir.rotate_45_normal()) {
//cout << "! " << dir.x << ' ' << dir.y << endl;
if (dir * point(j1 - j0, r - 1) == 0)
return {1, 1};
}
int cnt = 2;
for (point dir(1, 1); dir != point(-1, -1); dir = dir.rotate_90()) {
// (j0, 0) + dir * k = (j1, y0)
ll y0 = (j1 - j0) / dir.x * dir.y;
if (0 <= y0 && y0 < r)
cnt += 2;
// (j0, 0) + dir * k = (x1, r - 1)
ll x1 = j0 + (r - 1) / dir.y * dir.x;
if (0 <= x1 && x1 < c)
++cnt;
// (x2, 0) + dir * k = (j1, r - 1)
ll x2 = j1 - (r - 1) / dir.y * dir.x;
if (0 <= x2 && x2 < c)
++cnt;
}
if ((j0 + j1 + r) % 2) {
int jright = 2 * c - j1 - 1;
if (point(jright - j0, r - 1) * point(1, 1) >= 0)
++cnt;
int jleft = -j1 - 1;
if (point(-1, 1) * point(jleft - j0, r - 1) >= 0)
++cnt;
}
return {2, cnt};
}
const int MAXC = 1524;
int choose[MAXC * 2][MAXC * 2];
int balls_borders[MAXC][MAXC];
int choose_n0;
pair<int, int> bishop_goleft(int r, int c, int j0, int j1) {
if (j0 == c - 1 && j1 == 0 && r == c)
return {1, 1};
int loopcnt = max(0, r / (c - 1) / 2 - 3);
point pt(0, j0 + loopcnt * (c - 1) * 2);
int minmoves = 1 + loopcnt * 2;
int rmv = 0;
int lst = 0;
while (true) {
if ((point(j1, r - 1) - pt) * point(1, 1) >= 0) {
++minmoves;
lst = r - 1 - pt.y;
pt = pt + point(lst, lst);
rmv = abs(j1 - pt.x) / 2;
break;
}
minmoves += 2;
pt = pt + point(c - 1, c - 1);
if (point(-1, 1) * (point(j1, r - 1) - pt) >= 0) {
lst = r - 1 - pt.y;
pt = pt + point(-lst, lst);
rmv = abs(j1 - pt.x) / 2;
break;
}
pt = pt + point(1 - c, c - 1);
}
lst = c - 1 - lst;
int cnt = 0;
if (minmoves == 2)
return {2, 1};
for (int rm0 = 0; rm0 <= j0 && rm0 <= rmv; ++rm0) {
int Cvl = 0;
if (minmoves == 3) {
if (lst + rm0 >= rmv)
++cnt;
continue;
}
cnt = Add(cnt, balls_borders[minmoves - 4 - choose_n0][rmv - rm0]);
if (lst + rm0 < rmv) {
cnt = Sub(cnt, balls_borders[minmoves - 4 - choose_n0][rmv - rm0 - lst - 1]);
}
}
//cout << "---" << ' ' << minmoves << endl;
return {minmoves, cnt};
}
pair<int, int> bishop(int r, int c, int j0, int j1) {
if ((r + j0 + j1) % 2 == 0)
return {0, 0};
pair<int, int> ansup = bishop_goleft(r, c, j0, j1);
pair<int, int> ansdown = bishop_goleft(r, c, c - j0 - 1, c - j1 - 1);
if (ansup.first == ansdown.first)
return {ansup.first, Add(ansup.second, ansdown.second)};
return min(ansup, ansdown);
}
struct matrix {
matrix(int sz_): sz(sz_), f(sz_, vector<int>(sz_, 0)) {}
vector<int>& operator[](int i) {
return f[i];
}
matrix operator*(matrix m) {
matrix ans(sz);
for (int i = 0; i * 2 - 1 < sz; ++i) {
for (int t = 0; t < sz; ++t) {
if (f[i][t] == 0)
continue;
for (int j = 0; j < sz; ++j) {
ans[i][j] = Add(ans[i][j], Mul(m[t][j], f[i][t]));
}
}
}
for (int i = 0; i * 2 - 1 < sz; ++i) {
for (int j = 0; j < sz; ++j) {
ans[sz - i - 1][sz - j - 1] = ans[i][j];
}
}
return ans;
}
int sz;
vector<vector<int>> f;
};
matrix square(matrix a) {
int sz = a.sz;
matrix ans(sz);
for (auto i : {0, sz / 2, sz - 1}) {
for (int t = 0; t < sz; ++t) {
for (int j = 0; j < sz; ++j) {
ans[j][i] = ans[i][j] = Add(ans[i][j], Mul(a[t][j], a[i][t]));
}
}
}
for (int j = 1; j + 1 < sz; ++j) {
for (int i = 1; 2 * i < sz; ++i) {
ans[i][j] = 0;
for (int t = 0; t < sz; ++t) {
ans[i][j] = Add(ans[i][j], Mul(a[t][j], a[i][t]));
}
}
}
for (int i = 0; i * 2 - 1 < sz; ++i) {
for (int j = 0; j < sz; ++j) {
ans[sz - i - 1][sz - j - 1] = ans[i][j];
}
}
return ans;
for (int e=1; 2*e<sz; ++e) {
for (int s=1; s+1<sz; ++s) {
if (s-e>=0 && ans[s][e] != Add(ans[s-e][0], ans[s+1][e-1])) {
cerr << "HEY" << ' ' << ans[s][e] << ' ' << ans[s - e][0] << ' ' << ans[s + 1][e - 1] << " --- " << ans[s][e] - ans[s - e][0] - ans[s + 1][e - 1] << endl;
}
}
}
for (int i = 0; i < sz; ++i) {
for (int j = 0; j < sz; ++j) {
cout << ans[i][j] << ' ';
}
cout << endl;
}
return ans;
}
matrix mult_single(matrix a) {
matrix ans(a.sz);
for (int i = 0; i < a.sz; ++i) {
for (int j = 0; j < a.sz; ++j) {
ans[i][j] = a[i][j];
if (j)
ans[i][j] = Add(ans[i][j], a[i][j - 1]);
if (j + 1 < a.sz)
ans[i][j] = Add(ans[i][j], a[i][j + 1]);
}
}
return ans;
}
matrix pw(int sz, int m) {
matrix ans(sz);
for (int i = 0; i < sz; ++i)
ans[i][i] = 1;
for (int bt = 30; bt >= 0; --bt) {
ans = square(ans);
if (m & (1 << bt))
ans = mult_single(ans);
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int r, c, q;
cin >> r >> c >> q;
matrix king_ans(c);
king_ans = pw(c, r - 1);
choose_n0 = max(0, r / (c - 1) - c - 100);
for (int nadd = 0; nadd <= c * 2 + 1000; ++nadd) {
int n = choose_n0 + nadd;
choose[nadd][0] = 1;
for (int k = 1; k <= c * 2 + 1000 && k <= n; ++k) {
if (nadd == 0)
choose[nadd][k] = Div(Mul(choose[nadd][k - 1], n - k + 1), k);
else
choose[nadd][k] = Add(choose[nadd - 1][k], choose[nadd - 1][k - 1]);
}
}
for (int t = 0; t < c + 500; ++t) {
for (int p = 0; p < c + 500; ++p) {
balls_borders[t][p] = choose[p + t][p];
if (p)
balls_borders[t][p] = Add(balls_borders[t][p], balls_borders[t][p - 1]);
}
}
while (q--) {
char t;
int j0, j1;
cin >> t >> j0 >> j1;
--j0, --j1;
pair<int, int> ans;
if (t == 'P') {
ans = pawn(r, c, j0, j1);
} else if (t == 'Q') {
ans = queen(r, c, j0, j1);
} else if (t == 'R') {
ans = rook(r, c, j0, j1);
} else if (t == 'K') {
ans = {r - 1, king_ans[j0][j1]};
} else if (t == 'B') {
ans = bishop(r, c, j0, j1);
}
cout << ans.first << ' ' << ans.second << '\n';
}
}
Compilation message
chessrush.cpp: In function 'std::pair<int, int> bishop_goleft(int, int, int, int)':
chessrush.cpp:143:13: warning: unused variable 'Cvl' [-Wunused-variable]
143 | int Cvl = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
9428 KB |
Output is correct |
| 2 |
Execution timed out |
2088 ms |
10452 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
9420 KB |
Output is correct |
| 2 |
Correct |
15 ms |
11604 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9292 KB |
Output is correct |
| 4 |
Execution timed out |
2071 ms |
2912 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9300 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9484 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9428 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9300 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9484 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9428 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9556 KB |
Output is correct |
| 5 |
Execution timed out |
2063 ms |
16076 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
9896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
9896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
9896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
9896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
9428 KB |
Output is correct |
| 2 |
Execution timed out |
2088 ms |
10452 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
