QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243053 | #7334. Endgame | PetroTarnavskyi# | AC ✓ | 157ms | 59040kb | C++20 | 4.0kb | 2023-11-07 20:19:29 | 2023-11-07 20:19:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int INF = 1e9;
const int N = 1 << 18;
bool ok(int x)
{
return 0 <= x && x < 8;
}
struct State
{
int r1, c1, r2, c2, r3, c3;
bool isValid() const
{
return ok(r1) && ok(c1) && ok(r2) && ok(c2) && ok(r3) && ok(c3)
&& (abs(r3 - r1) > 1 || abs(c3 - c1) > 1)
&& (r2 != r1 || c2 != c1);
}
bool isRookCaptured() const
{
return r2 == r3 && c2 == c3;
}
bool isCheck() const
{
if (isRookCaptured())
return false;
if (r2 == r3)
return r2 != r1 || (c2 - c1) * (c3 - c1) > 0;
if (c2 == c3)
return c2 != c1 || (r2 - r1) * (r3 - r1) > 0;
return false;
}
bool blackCanMove() const
{
State nst = *this;
for (nst.r3 = r3 - 1; nst.r3 <= r3 + 1; nst.r3++)
for (nst.c3 = c3 - 1; nst.c3 <= c3 + 1; nst.c3++)
if ((nst.r3 != r3 || nst.c3 != c3) && nst.isValid() && !nst.isCheck())
return true;
return false;
}
bool isMate() const
{
return isCheck() && !blackCanMove();
}
bool isStalemate() const
{
return !isCheck() && !blackCanMove();
}
int getIdx() const
{
int idx = 0;
for (int x : {r1, c1, r2, c2, r3, c3})
idx = 8 * idx + x;
return idx;
}
};
VI gr[N][2];
int cntEdges[N];
int d[N][2];
void solve()
{
State st = {-1, -1, -1, -1, -1, -1};
FOR(i, 0, 8)
{
string s;
cin >> s;
FOR(j, 0, 8)
{
if (s[j] == 'W')
{
st.r1 = i;
st.c1 = j;
}
else if (s[j] == 'R')
{
st.r2 = i;
st.c2 = j;
}
else if (s[j] == 'B')
{
st.r3 = i;
st.c3 = j;
}
}
}
assert(st.isValid() && !st.isCheck());
int ans = d[st.getIdx()][0];
assert(ans != INF);
cout << ans << "\n";
}
void precalc()
{
queue<pair<int, int>> q;
FOR(i, 0, N)
FOR(j, 0, 2)
d[i][j] = INF;
FOR(r1, 0, 8) FOR(c1, 0, 8)
FOR(r2, 0, 8) FOR(c2, 0, 8)
FOR(r3, 0, 8) FOR(c3, 0, 8)
{
State st = {r1, c1, r2, c2, r3, c3};
if (!st.isValid())
continue;
int idx = st.getIdx();
if (st.isMate())
{
d[idx][1] = 0;
q.push({idx, 1});
continue;
}
if (st.isStalemate() || st.isRookCaptured())
continue;
State nst = st;
// White moves
// White king moves
for (nst.r1 = r1 - 1; nst.r1 <= r1 + 1; nst.r1++)
{
for (nst.c1 = c1 - 1; nst.c1 <= c1 + 1; nst.c1++)
{
if ((nst.r1 != r1 || nst.c1 != c1) && nst.isValid())
{
gr[nst.getIdx()][1].PB(idx);
}
}
}
// White rook moves
nst = st;
for (nst.r2 = 0; nst.r2 < 8; nst.r2++)
{
if (nst.r2 != r2 && (c2 != c1 || (r2 - r1) * (nst.r2 - r1) > 0))
{
gr[nst.getIdx()][1].PB(idx);
}
}
nst = st;
for (nst.c2 = 0; nst.c2 < 8; nst.c2++)
{
if (nst.c2 != c2 && (r2 != r1 || (c2 - c1) * (nst.c2 - c1) > 0))
{
gr[nst.getIdx()][1].PB(idx);
}
}
nst = st;
// Black moves
// Black king moves
for (nst.r3 = r3 - 1; nst.r3 <= r3 + 1; nst.r3++)
{
for (nst.c3 = c3 - 1; nst.c3 <= c3 + 1; nst.c3++)
{
if ((nst.r3 != r3 || nst.c3 != c3) && nst.isValid() && !nst.isCheck())
{
gr[nst.getIdx()][0].PB(idx);
cntEdges[idx]++;
}
}
}
}
while (!q.empty())
{
auto [v, p] = q.front();
q.pop();
for (int to : gr[v][p])
{
if (p)
{
if (d[to][0] == INF)
{
d[to][0] = d[v][1] + 1;
q.push({to, 0});
}
}
else
{
cntEdges[to]--;
if (cntEdges[to] == 0)
{
d[to][1] = d[v][0];
q.push({to, 1});
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
precalc();
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 140ms
memory: 58772kb
input:
2 ........ ........ ........ ........ ........ .......W R....... .......B ....B... ........ ..W..... ........ .....R.. ........ ........ ........
output:
1 2
result:
ok 2 number(s): "1 2"
Test #2:
score: 0
Accepted
time: 154ms
memory: 58704kb
input:
10 ........ ........ ........ ..R..... ....W... ........ .B...... ........ .......B ........ ...R.... ........ ........ ........ W....... ........ ........ .W...B.. ........ ........ ..R..... ........ ........ ........ .W...R.. ........ ........ ........ ......B. ........ ........ ........ ........
output:
7 10 9 11 11 12 11 12 14 7
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 152ms
memory: 59040kb
input:
10 ........ ...B.... ........ ......R. ........ ........ ..W..... ........ W....B.. ........ ........ ........ .R...... ........ ........ ........ ....R... ........ ..B..... ........ ........ ........ ........ .....W.. .R...... ........ ........ ........ ..B..... ........ ........ W....... ........
output:
12 9 14 13 7 7 11 13 7 7
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 134ms
memory: 58704kb
input:
10 ..B..... ........ ..W.R... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ..W..... ...R.... ..B..... ........ ........ ..R..... ........ ........ ..W..... ........ ..B..... ..B..... ...R.... W....... ........ ........ ........ ........ ........ B.......
output:
1 3 3 6 2 16 16 13 7 13
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 139ms
memory: 58708kb
input:
10 .R...... ..W..B.. ........ ........ ........ ........ ........ ........ ........ ........ ......W. ........ ........ ........ ...B.... ....R... ....W... ........ .......B ........ .....R.. ........ ........ ........ ........ ........ ........ ........ .......R ....B... ........ .W...... ........
output:
8 12 9 10 11 11 14 10 7 14
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 154ms
memory: 58748kb
input:
10 ........ ......W. ........ ..R..... ...B.... ........ ........ ........ ........ ........ ........ ........ ....R... .......B ...W.... ........ ........ ...B.... ........ ........ ........ ........ ......W. .....R.. W....... ........ ..B..... ........ ........ ........ .R...... ........ ........
output:
15 6 13 14 11 10 13 12 7 11
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 153ms
memory: 59024kb
input:
10 ........ ..W..... ....R... ........ ........ B....... ........ ........ ........ ........ ...W.... .......B ........ .R...... ........ ........ ........ ........ W......R ........ ........ ........ B....... ........ ........ ........ ........ ........ R....W.. ........ ...B.... ........ ........
output:
8 8 6 10 8 15 4 6 10 11
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 157ms
memory: 58744kb
input:
10 ........ ...B.... ........ ........ ........ R....... ...W.... ........ ....B... ........ .....R.. ..W..... ........ ........ ........ ........ R...W... ........ ........ ........ ........ .B...... ........ ........ ........ ........ ........ .......W ........ .....R.. ......B. ........ ........
output:
12 2 12 5 14 5 1 11 10 8
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 153ms
memory: 59040kb
input:
10 ....B... ........ ..W..... .......R ........ ........ ........ ........ ........ ........ ..W..... ........ R....... ........ ........ ......B. .....R.. ........ ........ .......B ........ ........ ........ .......W ........ .W...... ........ ........ ........ ..R..... .B...... ........ .B......
output:
7 9 9 9 5 12 13 7 9 14
result:
ok 10 numbers