QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#702411 | #9537. Chinese Chess | ucup-team173# | TL | 0ms | 0kb | C++20 | 4.0kb | 2024-11-02 15:56:22 | 2024-11-02 15:56:23 |
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});
}
}
}
}
}
}
string ans = "JSCMXB";
int n;
cin >> n;
vector<array<int, 3>> A;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
for(int j = 0; j < 6; j++) {
A.push_back({x, y, j});
}
}
while(1) {
using T = unordered_map<int, vector<array<int, 3>>>;
auto get = [&](int i, int j) {
T res;
for(auto [x, y, ty] : A) {
res[f[x][y][ty][i][j]].push_back({x, y, ty});
}
return res;
};
auto eval = [&](T mp) -> pair<int, int> {
if(mp.size() == 0) return {1e9, 1e9};
pair<int, int> mx = {-1, -1};
for(auto [k, v] : mp) {
int sz = v.size();
set<int> tys;
for(auto [x, y, ty] : v) tys.insert(ty);
mx = max(mx, {(int)tys.size(), sz});
}
return mx;
};
T mp;
int qx, qy;
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 9; j++) {
auto now = get(i, j);
if(eval(mp) > eval(now)) {
mp = now;
qx = i, qy = j;
}
}
}
cout << "? " << qx << ' ' << qy << endl;
int res;
cin >> res;
A = mp[res];
set<int> tys;
for(auto [x, y, ty] : A) tys.insert(ty);
if(tys.size() == 1) {
cout << "! " << ans[*tys.begin()] << endl;
break;
}
}
}
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
output:
? 1 8