QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750649 | #9537. Chinese Chess | PlentyOfPenalty# | TL | 25ms | 4252kb | C++20 | 5.4kb | 2024-11-15 15:19:36 | 2024-11-15 15:19:36 |
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 (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;
while (con > 0) {
if (con > 2) {
int p = ask(0);
s = G[0][p] & s;
} 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("C.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;
#endif
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 4216kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 9ms
memory: 3924kb
input:
4 2 1 2 3 2 5 2 7 5 1
output:
2 ? 0 0 ? 0 6 ! M
result:
ok number is guessed.
Test #3:
score: 0
Accepted
time: 3ms
memory: 3912kb
input:
1 2 4 -1 1
output:
2 ? 0 0 ? 0 2 ! X
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 3ms
memory: 3976kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 2ms
memory: 4008kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 2ms
memory: 4204kb
input:
2 7 7 1 0 -1 6
output:
2 ? 0 0 ? 7 2 ! S
result:
ok number is guessed.
Test #7:
score: 0
Accepted
time: 15ms
memory: 4220kb
input:
5 8 6 1 3 0 5 2 4 0 2 6 3
output:
2 ? 0 0 ? 0 3 ! J
result:
ok number is guessed.
Test #8:
score: 0
Accepted
time: 15ms
memory: 4200kb
input:
6 0 7 1 6 2 8 0 5 7 6 8 2 -1 14
output:
2 ? 0 0 ? 8 1 ! B
result:
ok number is guessed.
Test #9:
score: 0
Accepted
time: 20ms
memory: 3960kb
input:
7 6 5 3 0 3 2 4 1 4 0 2 4 5 2 5 7
output:
2 ? 0 0 ? 0 4 ! J
result:
ok number is guessed.
Test #10:
score: 0
Accepted
time: 25ms
memory: 4156kb
input:
8 3 3 2 5 6 2 7 4 1 4 3 0 2 4 3 4 7 -1
output:
2 ? 0 1 ? 0 0 ! S
result:
ok number is guessed.
Test #11:
score: 0
Accepted
time: 19ms
memory: 4004kb
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8 6 8
output:
2 ? 2 0 ? 0 0 ! J
result:
ok number is guessed.
Test #12:
score: 0
Accepted
time: 22ms
memory: 4012kb
input:
10 4 0 0 0 5 0 7 0 8 0 1 0 6 0 9 0 2 0 3 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #13:
score: 0
Accepted
time: 20ms
memory: 4012kb
input:
9 1 8 1 2 1 5 1 6 1 3 1 4 1 0 1 1 1 7 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #14:
score: 0
Accepted
time: 14ms
memory: 3940kb
input:
10 0 4 5 4 8 4 2 4 4 4 7 4 3 4 9 4 6 4 1 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #15:
score: 0
Accepted
time: 23ms
memory: 3952kb
input:
9 4 6 4 5 4 7 4 4 4 1 4 3 4 0 4 8 4 2 6 12
output:
2 ? 4 2 ? 0 0 ! J
result:
ok number is guessed.
Test #16:
score: 0
Accepted
time: 21ms
memory: 4020kb
input:
10 9 2 5 2 1 2 8 2 6 2 7 2 2 2 0 2 4 2 3 2 10 3
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #17:
score: 0
Accepted
time: 18ms
memory: 4220kb
input:
9 3 1 3 7 3 5 3 3 3 6 3 4 3 0 3 2 3 8 6 11
output:
2 ? 3 2 ? 0 0 ! J
result:
ok number is guessed.
Test #18:
score: 0
Accepted
time: 21ms
memory: 4048kb
input:
10 5 1 8 1 6 1 4 1 3 1 0 1 2 1 7 1 9 1 1 1 10 -1
output:
2 ? 9 0 ? 0 0 ! B
result:
ok number is guessed.
Test #19:
score: 0
Accepted
time: 20ms
memory: 3952kb
input:
9 1 6 1 4 1 3 1 7 1 8 1 5 1 2 1 1 1 0 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #20:
score: 0
Accepted
time: 22ms
memory: 3944kb
input:
10 5 0 9 0 1 0 2 0 3 0 6 0 7 0 4 0 0 0 8 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #21:
score: 0
Accepted
time: 19ms
memory: 4208kb
input:
9 0 3 0 5 0 7 0 0 0 4 0 8 0 1 0 6 0 2 6 5
output:
2 ? 0 0 ? 0 1 ! J
result:
ok number is guessed.
Test #22:
score: 0
Accepted
time: 23ms
memory: 4252kb
input:
10 1 0 9 0 4 0 2 0 8 0 7 0 5 0 3 0 0 0 6 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #23:
score: 0
Accepted
time: 19ms
memory: 4048kb
input:
9 1 8 1 2 1 7 1 0 1 4 1 6 1 1 1 5 1 3 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #24:
score: 0
Accepted
time: 17ms
memory: 3944kb
input:
10 2 4 1 4 0 4 6 4 4 4 9 4 5 4 3 4 7 4 8 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #25:
score: 0
Accepted
time: 16ms
memory: 4204kb
input:
9 0 2 0 7 0 5 0 4 0 0 0 3 0 1 0 6 0 8 6 5
output:
2 ? 0 0 ? 0 1 ! J
result:
ok number is guessed.
Test #26:
score: 0
Accepted
time: 19ms
memory: 3948kb
input:
10 5 3 2 3 3 3 8 3 9 3 1 3 6 3 7 3 0 3 4 3 11 4
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #27:
score: -100
Time Limit Exceeded
input:
50 7 5 9 2 0 4 9 3 8 4 8 2 7 2 6 4 4 4 0 0 1 7 1 1 1 5 2 0 9 8 9 0 3 1 7 8 8 6 5 0 7 3 8 5 2 6 4 8 3 5 6 8 0 8 5 7 4 6 1 6 3 8 5 6 3 0 5 3 0 7 5 1 3 4 0 1 7 6 2 3 4 3 5 5 8 1 0 3 6 5 9 5 5 8 7 4 6 3 2 7 -1 -1 -1
output:
3 ? 0 0 ? 0 0 ? 0 0 ? 0 0