QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#707770 | #9537. Chinese Chess | ucup-team173 | TL | 0ms | 0kb | C++20 | 5.2kb | 2024-11-03 17:28:18 | 2024-11-03 17:28:20 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
auto valid = [&](int x, int y) {
return 0 <= x && x < 10 && 0 <= y && y < 9;
};
auto getTo = [&](int x, int y, int ty) {
vector<pair<int, int>> tmp;
if(ty == 0) {
for(int i = -1; i <= 1; i += 2) {
tmp.push_back({x + i, y});
tmp.push_back({x, y + i});
}
} else if(ty == 1) {
for(int i = -1; i <= 1; i += 2) {
for(int j = -1; j <= 1; j += 2) {
tmp.push_back({x + i, y + j});
}
}
} else if(ty == 2) {
for(int r = 0; r < 10; r++) if(r != x) tmp.push_back({r, y});
for(int c = 0; c < 9; c++) if(c != y) tmp.push_back({x, c});
} else if(ty == 3) {
for(int i = -2; i <= 2; i += 4) {
for(int j = -1; j <= 1; j += 2) {
tmp.push_back({x + i, y + j});
tmp.push_back({x + j, y + i});
}
}
} else if(ty == 4) {
for(int i = -2; i <= 2; i += 4) {
for(int j = -2; j <= 2; j += 4) {
tmp.push_back({x + i, y + j});
}
}
} else {
tmp.push_back({x + 1, y});
if(x > 4) {
tmp.push_back({x, y + 1});
tmp.push_back({x, y - 1});
}
}
vector<pair<int, int>> res;
for(auto [x, y] : tmp) if(valid(x, y)) res.push_back({x, y});
return res;
};
vector f(10, vector(9, vector(6, vector(10, vector(9, -1)))));
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 9; j++) {
for(int ty = 0; ty < 6; ty++) {
auto &g = f[i][j][ty];
queue<pair<int, int>> q;
q.push({i, j});
g[i][j] = 0;
while(q.size()) {
auto [x, y] = q.front(); q.pop();
for(auto [tx, ty] : getTo(x, y, ty)) {
if(g[tx][ty] == -1) {
g[tx][ty] = g[x][y] + 1;
q.push({tx, ty});
}
}
}
}
}
}
int n;
cin >> n;
constexpr int N = 540;
using B = bitset<N>;
auto id = [&](int x, int y, int ty) {
return (x * 9 + y) * 6 + ty;
};
auto rid = [&](int id) {
return make_tuple(id / 6 / 9, id / 6 % 9, id % 6);
};
B A;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
for(int j = 0; j < 6; j++) {
A[id(x, y, j)] = 1;
}
}
A.flip();
using T = unordered_map<int, B>;
unordered_map<B, int> mp, g;
unordered_map<B, T> G;
unordered_map<B, pair<int, int>> best;
auto print = [&](B A) {
for(int id = A._Find_first(); id < N; id = A._Find_next(id)) {
auto [x, y, t] = rid(id);
cerr << " " << x << ' ' << y << ' ' << t << endl;
}
};
// print(A);
auto get = [&](int i, int j, B &A) {
T res;
for(int id = A._Find_first(); id < N; id = A._Find_next(id)) {
auto [x, y, t] = rid(id);
res[f[x][y][t][i][j]][id] = 1;
}
return res;
};
auto getty = [&](B A) {
vector<int> tys(6, 0);
for(int i = A._Find_first(); i < N; i = A._Find_next(i)) {
auto [x, y, ty] = rid(i);
tys[ty]++;
}
if(accumulate(tys.begin(), tys.end(), 0) > 1) return -1;
for(int i = 0; i < 6; i++) if(tys[i]) return i;
};
auto dfs1 = [&](auto self, B A, int dep, int mxdep) {
if(dep > mxdep) return 10;
if(g.count(A)) return g[A];
if(getty(A) != -1) return g[A] = 0;
// cerr << dep << '\n';
g[A] = 10;
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 9; j++) {
auto nG = get(i, j, A);
if(nG.size() == 1) continue;
int mx = 0;
for(auto [k, v] : nG) {
mx = max(mx, self(self, v, dep + 1, mxdep) + 1);
}
if(mx < g[A]) {
g[A] = mx;
best[A] = {i, j};
G[A] = nG;
}
}
}
return g[A];
};
dfs1(dfs1, A, 0, 3);
cout << g[A] << endl;
// cerr << g.size() << endl;
// cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
// return;
auto dfs2 = [&](auto self, B A) {
// print(A);
// cerr << g[A] << '\n';
if(getty(A) != -1) {
cout << "! " << "JSCMXB"[getty(A)] << endl;
return;
}
auto [x, y] = best[A];
cout << "? " << x << ' ' << y << endl;
int res;
cin >> res;
self(self, G[A][res]);
};
dfs2(dfs2, A);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
1 9 0