#include <bits/stdc++.h>
using namespace std;
constexpr size_t N = 100;
constexpr int64_t INF = 1LL << 42, MOD = 1000000007;
template <size_t L>
struct Matrix
{
int64_t m[L][L][2];
Matrix operator*(Matrix const &b) const
{
Matrix c;
for (size_t i = 0; i < L; ++i)
for (size_t j = 0; j < L; ++j)
c.m[i][j][0] = INF, c.m[i][j][1] = 0;
for (size_t i = 0; i < L; ++i)
for (size_t j = 0; j < L; ++j)
for (size_t k = 0; k < L; ++k)
{
if (m[i][k][0] + b.m[k][j][0] < c.m[i][j][0])
c.m[i][j][0] = m[i][k][0] + b.m[k][j][0], c.m[i][j][1] = 0;
if (m[i][k][0] + b.m[k][j][0] == c.m[i][j][0])
c.m[i][j][1] = (c.m[i][j][1] + m[i][k][1] * b.m[k][j][1]) % MOD;
}
return c;
}
array<int64_t[2], L> operator*(array<int64_t[2], L> const &b)
{
array<int64_t[2], L> c;
for (size_t i = 0; i < L; ++i)
c[i][0] = INF, c[i][1] = 0;
for (size_t i = 0; i < L; ++i)
for (size_t j = 0; j < L; ++j)
{
if (m[i][j][0] + b[j][0] < c[i][0])
c[i][0] = m[i][j][0] + b[j][0], c[i][1] = 0;
if (m[i][j][0] + b[j][0] == c[i][0])
c[i][1] = (c[i][1] + m[i][j][1] * b[j][1]) % MOD;
}
return c;
}
};
Matrix<2 * N> bpow[31];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int r, c, q;
cin >> r >> c >> q;
// Build min matrix for bishop
for (size_t i = 0; i < 2 * N; ++i)
for (size_t j = 0; j < 2 * N; ++j)
{
bpow[1].m[i][j][0] = INF;
bpow[1].m[i][j][1] = 0;
}
for (size_t i = 0; i < c; ++i)
{
// d = 0
if (i + 1 < c)
{
bpow[1].m[i][i + 1][0] = 0;
bpow[1].m[i][i + 1][1] = 1;
bpow[1].m[i][i + 1 + N][0] = 1;
bpow[1].m[i][i + 1 + N][1] = 1;
}
// d = 1
if (i)
{
bpow[1].m[i + N][i - 1][0] = 1;
bpow[1].m[i + N][i - 1][1] = 1;
bpow[1].m[i + N][i - 1 + N][0] = 0;
bpow[1].m[i + N][i - 1 + N][1] = 1;
}
}
for (size_t i = 2; i < 31; ++i)
bpow[i] = bpow[i - 1] * bpow[i - 1];
while (q--)
{
char type;
int start, finish;
cin >> type >> start >> finish;
switch (type)
{
case 'P':
{
if (start == finish)
cout << r - 1 << " 1\n";
else
cout << "0 0\n";
break;
}
case 'R':
{
if (start == finish)
cout << "1 1\n";
else
cout << "2 2\n";
break;
}
case 'Q':
{
if (start == finish || abs(start - finish) == (r - 1))
cout << "1 1\n";
else
{
int ans = 4 + (r == c) * ((start == 1 || start == c) + (finish == 1 || finish == c));
if ((r - abs(start - finish)) & 1)
{
int side_space = (r - 1 - abs(start - finish)) / 2;
ans += min(start, finish) - side_space >= 1;
ans += max(start, finish) + side_space <= c;
}
cout << "2 " << ans << '\n';
}
break;
}
case 'B':
{
array<int64_t[2], 2 * N> state;
for (size_t i = 0; i < 2 * N; ++i)
state[i][0] = INF, state[i][1] = 0;
state[start - 1][0] = 1;
state[start - 1][1] = 1;
state[start - 1 + N][0] = 1;
state[start - 1 + N][1] = 1;
size_t k = r - 1, i = 1;
while (k)
{
if (k & 1)
state = bpow[i] * state;
++i;
k >>= 1;
}
int64_t num_turns = min(state[finish - 1][0], state[finish - 1 + N][0]),
num_ways = 0;
if (state[finish - 1][0] == num_turns)
num_ways += state[finish - 1][1];
if (state[finish - 1 + N][0] == num_turns)
num_ways += state[finish - 1 + N][1];
if (num_turns == INF)
cout << "0 0\n";
else
cout << num_turns << ' ' << num_ways << '\n';
break;
}
}
}
}
Compilation message
chessrush.cpp: In function 'int main()':
chessrush.cpp:70:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | for (size_t i = 0; i < c; ++i)
| ~~^~~
chessrush.cpp:73:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
73 | if (i + 1 < c)
| ~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
19660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
208 ms |
19680 KB |
Output is correct |
| 2 |
Correct |
220 ms |
19684 KB |
Output is correct |
| 3 |
Correct |
213 ms |
19636 KB |
Output is correct |
| 4 |
Correct |
539 ms |
19660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
19660 KB |
Output is correct |
| 2 |
Correct |
274 ms |
19704 KB |
Output is correct |
| 3 |
Correct |
229 ms |
19636 KB |
Output is correct |
| 4 |
Correct |
252 ms |
19648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
19660 KB |
Output is correct |
| 2 |
Correct |
274 ms |
19704 KB |
Output is correct |
| 3 |
Correct |
229 ms |
19636 KB |
Output is correct |
| 4 |
Correct |
252 ms |
19648 KB |
Output is correct |
| 5 |
Incorrect |
1045 ms |
19732 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
19628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
19628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
19628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
19628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
19660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
