QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #701778 | #9537. Chinese Chess | ucup-team5052# | RE | 1ms | 3856kb | C++14 | 4.8kb | 2024-11-02 14:42:01 | 2024-11-02 14:42:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int R = 9, C = 8;
int n, sx[99], sy[99], dis[6][99][10][9], xsq[99], ysq[99], qsz;
const string ANS = "JSCMXB";
unordered_map <string, int> vis;
string ssq[6][99], rs;
int hs[6][99];
vector <pair <int, int> > getNext(int x, int y, int t) {
vector <pair <int, int> > res;
if (t == 0) {
// King
res.push_back(make_pair(x - 1, y));
res.push_back(make_pair(x + 1, y));
res.push_back(make_pair(x, y - 1));
res.push_back(make_pair(x, y + 1));
} else if (t == 1) {
// Mandarin
res.push_back(make_pair(x - 1, y - 1));
res.push_back(make_pair(x + 1, y - 1));
res.push_back(make_pair(x - 1, y + 1));
res.push_back(make_pair(x + 1, y + 1));
} else if (t == 2) {
// Rook
for (int i = 0;i < R;i++) {
if (i != x) res.push_back(make_pair(i, y));
}
for (int j = 0;j < C;j++) {
if (j != y) res.push_back(make_pair(x, j));
}
} else if (t == 3) {
// Knight
res.push_back(make_pair(x - 1, y - 2));
res.push_back(make_pair(x - 2, y - 1));
res.push_back(make_pair(x - 1, y + 2));
res.push_back(make_pair(x - 2, y + 1));
res.push_back(make_pair(x + 1, y - 2));
res.push_back(make_pair(x + 2, y - 1));
res.push_back(make_pair(x + 1, y + 2));
res.push_back(make_pair(x + 2, y + 1));
} else if (t == 4) {
// Bishop
res.push_back(make_pair(x - 2, y - 2));
res.push_back(make_pair(x + 2, y - 2));
res.push_back(make_pair(x - 2, y + 2));
res.push_back(make_pair(x + 2, y + 2));
} else if (t == 5) {
// Pawn
if (x <= 4) res.push_back(make_pair(x + 1, y));
else {
res.push_back(make_pair(x, y - 1));
res.push_back(make_pair(x, y + 1));
res.push_back(make_pair(x + 1, y));
}
}
return res;
}
inline void Bfs(int tp, int idx) {
memset(dis[tp][idx], 0x3f, sizeof(dis[tp][idx]));
queue <pair <int, int> > que;
dis[tp][idx][sx[idx]][sy[idx]] = 0;
que.push(make_pair(sx[idx], sy[idx]));
while (!que.empty()) {
int cx = que.front().first, cy = que.front().second;
que.pop();
auto nxt = getNext(cx, cy, tp);
for (auto [tx, ty] : nxt) {
if (tx < 0 || tx > R || ty < 0 || ty > C) continue;
if (dis[tp][idx][cx][cy] + 1 < dis[tp][idx][tx][ty]) {
dis[tp][idx][tx][ty] = dis[tp][idx][cx][cy] + 1;
que.push(make_pair(tx, ty));
}
}
}
// for (int i = 0;i <= R;i++) {
// for (int j = 0;j <= C;j++) {
// cout << dis[tp][idx][i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
}
inline void Read() {
cin >> n;
for (int i = 1;i <= n;i++) cin >> sx[i] >> sy[i];
}
inline bool Dfs(int curx, int cury, int lft, bool fixed) {
if (curx > R) {
if(fixed)
{
vis.clear();
for (int i = 0;i < 6;i++) {
for (int j = 1;j <= n;j++) {
// cout << (int)ssq[i][j][0] << endl;
if (vis[ssq[i][j]]) return 0;
}
for (int j = 1;j <= n;j++) vis[ssq[i][j]] = 1;
}
}
else
{
static bool vis[2000010];
for(int i=0;i<6;i++)
for(int j=1;j<=n;j++)
vis[hs[i][j]]=0;
for(int i=0;i<6;i++)
{
for(int j=1;j<=n;j++)
if(vis[hs[i][j]]) return 0;
for(int j=1;j<=n;j++) vis[hs[i][j]]=1;
}
}
return 1;
}
if ((R + 1) * (C + 1) - (curx * (C + 1) + cury) + 1 < lft) return 0;
if (Dfs(curx + (cury == C), (cury + 1) % (C + 1), lft, fixed)) return 1;
if (!lft) return 0;
if(fixed)
{
if(lft == 4 && (curx != 4 || cury != 6)) return 0;
if(lft == 3 && (curx != 4 || cury != 7)) return 0;
if(lft == 2 && (curx != 9 || cury != 0)) return 0;
if(lft == 1 && (curx != 9 || cury != 7)) return 0;
}
qsz++;
xsq[qsz] = curx; ysq[qsz] = cury;
for (int i = 0;i < 6;i++) {
for (int j = 1;j <= n;j++) {
int x = min(101, dis[i][j][curx][cury]);
ssq[i][j][qsz - 1] = (char)x;
hs[i][j] = hs[i][j] * 102 + x;
}
}
if (Dfs(curx + (cury == C), (cury + 1) % (C + 1), lft - 1, fixed)) return 1;
for(int i=0;i<6;i++)
for(int j=1;j<=n;j++)
hs[i][j]/=102;
qsz--;
return 0;
}
inline void Solve() {
for (int i = 0;i < 6;i++) {
for (int j = 1;j <= n;j++) Bfs(i, j);
}
for (int cnt = 1;cnt <= 10;cnt++) {
for (int i = 0;i < 6;i++) {
for (int j = 1;j <= n;j++) ssq[i][j].resize(cnt);
}
if (Dfs(0, 0, cnt, cnt == 4)) {
cout << qsz << endl;
string qres = "";
for (int j = 1;j <= qsz;j++) {
cout << "? " << xsq[j] << " " << ysq[j] << endl;
int val;
cin >> val;
if (val == -1) val = 101;
qres.push_back((char)val);
}
for (int i = 0;i < 6;i++) {
for (int j = 1;j <= n;j++) {
if (ssq[i][j] == qres) {
cout << "! " << ANS[i] << endl;
return;
}
}
}
}
}
}
inline void ReadTest() {
n = 90;
for (int i = 1;i <= n;i++) {
sx[i] = (i - 1) / (C + 1);
sy[i] = (i - 1) % (C + 1);
}
}
int main() {
Read();
Solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3720kb
input:
1 9 0 6
output:
1 ? 7 6 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
4 2 1 2 3 2 5 2 7 5 4
output:
2 ? 4 8 ? 7 6 ! M
result:
ok number is guessed.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
1 2 4 -1 9
output:
2 ? 4 8 ? 8 7 ! B
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
1 6 0 6
output:
1 ? 4 6 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
2 7 7 1 0 -1 12
output:
2 ? 4 8 ? 8 5 ! B
result:
ok number is guessed.
Test #7:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
5 8 6 1 3 0 5 2 4 0 2 4 5
output:
2 ? 4 8 ? 8 3 ! M
result:
ok number is guessed.
Test #8:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
6 0 7 1 6 2 8 0 5 7 6 8 2 -1 12
output:
2 ? 4 4 ? 9 8 ! B
result:
ok number is guessed.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
7 6 5 3 0 3 2 4 1 4 0 2 4 5 2 2 9
output:
2 ? 3 3 ? 8 7 ! J
result:
ok number is guessed.
Test #10:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
8 3 3 2 5 6 2 7 4 1 4 3 0 2 4 3 4 7 -1
output:
2 ? 4 7 ? 7 7 ! S
result:
ok number is guessed.
Test #11:
score: -100
Runtime Error
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8
output:
3 ? 4 7