QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750719 | #9537. Chinese Chess | PlentyOfPenalty# | RE | 0ms | 0kb | C++20 | 5.5kb | 2024-11-15 15:36:59 | 2024-11-15 15:37:01 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) ((void)(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
using lll = __int128;
const char name[] = {'J', 'S', 'C', 'M', 'X', 'B'};
int F[540][90];
vector<int> g[6][90];
int id(int x, int y) { return x * 9 + y; }
pair<int, int> pos(int k) { return make_pair(k / 9, k % 9); }
using status = bitset<540>;
status G[90][19];
unordered_map<status, pair<int, int>> mp;
int dfs(const status &u, int dep) {
// cerr << "dfs " << u << endl;
int c = -1;
for (int i = u._Find_first(); i != 540; i = u._Find_next(i)) {
if (c == -1) {
c = i / 90;
} else if (c != i / 90) {
c = -2;
break;
}
}
if (c != -2) return 0;
if (dep >= 2) return 114514;
auto it = mp.find(u);
if (it != mp.end()) {
return it->second.first;
}
int mn = INT_MAX, cho = -1;
for (int y = 0; y < 90; y++) {
int mx = -1;
for (int i = 0; i < 19; i++) {
status v = G[y][i] & u;
if (u == v || v.count() == 0) continue;
mx = max(mx, dfs(v, dep + 1) + 1);
// if (dep == 0) {
// log("finish y=%d i=%d mx=%d\n", y, i, mx);
// }
}
// if (dep == 0) {
// log("finish y=%d mx=%d\n", y, mx);
// }
if (mx != -1 && mx < mn) {
mn = mx;
cho = y;
}
}
// if (mn >= 3 && mn <= 100) {
// cerr << u << " " << mn << endl;
// }
mp[u] = make_pair(mn, cho);
return mn;
}
int _x, _y, _c;
int ask(int i) {
#ifdef memset0
return F[_c * 90 + id(_x, _y)][i];
#else
auto [x, y] = pos(i);
cout << "? " << x << " " << y << endl;
cout << flush;
int t;
cin >> t;
return t + 1;
#endif
}
int solve(status s) {
int con = dfs(s, 0);
int stp = con > 2 ? 3 : con;
cout << stp << endl;
cout << flush;
mp.clear();
while (con > 0) {
if (con > 2) {
int p = ask(0);
s = G[0][p] & s;
assert(dfs(s, 0) <= 2);
} else {
int i = mp[s].second;
int p = ask(i);
s = G[i][p] & s;
}
--stp;
con = dfs(s, 0);
}
assert(stp >= 0);
while (stp--) {
ask(89);
}
int c = -1;
for (int i = s._Find_first(); i != 540; i = s._Find_next(i)) {
if (c == -1) {
c = i / 90;
} else if (c != i / 90) {
c = -2;
break;
}
}
return c;
}
int main() {
#ifdef memset0
freopen("C2.in", "r", stdin);
// freopen("C.out", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(0);
for (int c = 0; c < 6; c++)
for (int x = 0; x < 10; x++)
for (int y = 0; y < 9; y++) {
int i = id(x, y);
auto push = [&](int x, int y) {
if (x < 0 || y < 0 || x >= 10 || y >= 9) return;
g[c][i].emplace_back(id(x, y));
};
if (c == 0) {
push(x + 1, y);
push(x - 1, y);
push(x, y + 1);
push(x, y - 1);
} else if (c == 1) {
push(x + 1, y + 1);
push(x - 1, y + 1);
push(x + 1, y - 1);
push(x - 1, y - 1);
} else if (c == 2) {
for (int t = 0; t < 10; t++) {
if (t != x) push(t, y);
}
for (int t = 0; t < 9; t++) {
if (t != y) push(x, t);
}
} else if (c == 3) {
push(x + 2, y + 1);
push(x - 2, y + 1);
push(x + 2, y - 1);
push(x - 2, y - 1);
push(x + 1, y + 2);
push(x - 1, y + 2);
push(x + 1, y - 2);
push(x - 1, y - 2);
} else if (c == 4) {
push(x + 2, y + 2);
push(x - 2, y + 2);
push(x + 2, y - 2);
push(x - 2, y - 2);
} else {
if (x <= 4) {
push(x + 1, y);
} else {
push(x + 1, y);
push(x, y - 1);
push(x, y + 1);
}
}
}
for (int i = 0; i < 540; i++) {
auto [x, y] = pos(i % 90);
int c = i / 90;
fill(all(F[i]), -1);
F[i][id(x, y)] = 0;
queue<int> q;
q.push(id(x, y));
// log("! c = %d x = %d y = %d\n", c, x, y);
while (q.size()) {
int u = q.front();
q.pop();
// log("F[%d][%d,%d] = %d\n", i, pos(u).first, pos(u).second, F[i][u]);
for (int v : g[c][u])
if (F[i][v] == -1) {
F[i][v] = F[i][u] + 1;
q.push(v);
}
}
}
for (int i = 0; i < 540; i++)
for (int j = 0; j < 90; j++) {
F[i][j]++;
assert(F[i][j] < 19);
G[j][F[i][j]].set(i);
}
// for (int i = 0; i < 540; i++)
// for (int j = 0; j < 90; j++) {
// printf("F[%d][%d] = %d\n", i, j, F[i][j]);
// }
// return 0;
// {
// status s;
// s.set();
// cout << dfs(s, 0) << endl;
// exit(0);
// }
status s;
int n;
cin >> n;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
for (int c = 0; c < 6; c++) {
s.set(c * 90 + x[i] * 9 + y[i]);
}
}
log(">> n=%d\n", n);
#ifdef memset0
for (int i = 0; i < n; i++) {
_x = x[i];
_y = y[i];
for (_c = 0; _c < 6; _c++) {
log("test (%d, %d) %d\n", _x, _y, _c);
int c = solve(s);
log("test (%d, %d) %d -> %d\n", _x, _y, _c, c);
assert(c == _c);
}
}
#else
int res = solve(s);
cout << "! " << name[res] << endl;
cout << flush;
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
1 9 0 -1
output:
1 ? 0 0 ? 1 0