QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#704756 | #9537. Chinese Chess | ucup-team5062# | WA | 3ms | 4264kb | C++20 | 5.1kb | 2024-11-02 20:55:59 | 2024-11-02 20:56:00 |
Judging History
answer
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Candidates {
pair<long long, long long> x[6];
};
vector<pair<int, int>> Movements[7];
int Dist[90][90][6];
Candidates Vec[90][30];
// ================================================================================== Initialize
void Initialize() {
Movements[0].push_back(make_pair(+1, 0));
Movements[0].push_back(make_pair(-1, 0));
Movements[0].push_back(make_pair(0, +1));
Movements[0].push_back(make_pair(0, -1));
Movements[1].push_back(make_pair(+1, +1));
Movements[1].push_back(make_pair(-1, +1));
Movements[1].push_back(make_pair(+1, -1));
Movements[1].push_back(make_pair(-1, -1));
for (int i = -9; i <= 9; i++) {
if (i == 0) continue;
Movements[2].push_back(make_pair(i, 0));
Movements[2].push_back(make_pair(0, i));
}
Movements[3].push_back(make_pair(+2, -1));
Movements[3].push_back(make_pair(+2, +1));
Movements[3].push_back(make_pair(+1, -2));
Movements[3].push_back(make_pair(+1, +2));
Movements[3].push_back(make_pair(-2, -1));
Movements[3].push_back(make_pair(-2, +1));
Movements[3].push_back(make_pair(-1, -2));
Movements[3].push_back(make_pair(-1, +2));
Movements[4].push_back(make_pair(+2, +2));
Movements[4].push_back(make_pair(+2, -2));
Movements[4].push_back(make_pair(-2, +2));
Movements[4].push_back(make_pair(-2, -2));
Movements[5].push_back(make_pair(1, 0));
Movements[6].push_back(make_pair(1, 0));
Movements[6].push_back(make_pair(0, -1));
Movements[6].push_back(make_pair(0, +1));
}
void get_shortest(int stt, int koma) {
for (int i = 0; i < 90; i++) Dist[stt][i][koma] = (1 << 30);
queue<int> Q; Q.push(stt);
Dist[stt][stt][koma] = 1;
while (!Q.empty()) {
int pos = Q.front(); Q.pop();
int sx = pos / 9;
int sy = pos % 9;
int mv = ((koma == 5 && sx >= 5) ? 6 : koma);
// Move
for (int i = 0; i < Movements[mv].size(); i++) {
int cx = sx + Movements[mv][i].first;
int cy = sy + Movements[mv][i].second;
if (cx < 0 || cy < 0 || cx > 9 || cy > 8) continue;
int val = cx * 9 + cy;
if (Dist[stt][val][koma] == (1 << 30)) {
Dist[stt][val][koma] = Dist[stt][pos][koma] + 1;
Q.push(val);
}
}
}
}
void Prepare() {
for (int cell = 0; cell < 90; cell++) {
for (int koma = 0; koma < 6; koma++) {
for (int i = 0; i < 90; i++) {
int dst = (Dist[i][cell][koma] == (1 << 30) ? 0 : Dist[i][cell][koma]);
if (i < 45) Vec[cell][dst].x[koma].first += (1LL << i);
else Vec[cell][dst].x[koma].second += (1LL << (i - 45));
}
}
}
}
// ================================================================================== Apply
Candidates Apply(Candidates a, int cell, int dst) {
for (int i = 0; i < 6; i++) {
a.x[i].first &= Vec[cell][dst].x[i].first;
a.x[i].second &= Vec[cell][dst].x[i].second;
}
return a;
}
pair<bool, int> Solve(int dep, int prv, Candidates a) {
if (dep == 0) return make_pair(false, -1);
// Recursion
for (int cell = prv; cell < 90; cell++) {
bool flag = true;
for (int dst = 0; dst <= 18; dst++) {
Candidates b = Apply(a, cell, dst);
int cnt = 0;
if (b.x[0] == make_pair(0LL, 0LL)) cnt++;
if (b.x[1] == make_pair(0LL, 0LL)) cnt++;
if (b.x[2] == make_pair(0LL, 0LL)) cnt++;
if (b.x[3] == make_pair(0LL, 0LL)) cnt++;
if (b.x[4] == make_pair(0LL, 0LL)) cnt++;
if (b.x[5] == make_pair(0LL, 0LL)) cnt++;
if (cnt <= 4 && Solve(dep - 1, cell + 1, b) == make_pair(false, -1)) { flag = false; break; }
}
if (flag == true) return make_pair(true, cell);
}
return make_pair(false, -1);
}
// ================================================================================== Main Function
int main() {
// Step 1. Input
int N; cin >> N;
vector<int> X(N, 0);
vector<int> Y(N, 0);
for (int i = 0; i < N; i++) cin >> X[i] >> Y[i];
Initialize();
for (int i = 0; i < 90; i++) {
for (int j = 0; j < 6; j++) get_shortest(i, j);
}
Prepare();
// Step 2. Solve
Candidates Z;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 6; j++) {
int cur = X[i] * 9 + Y[i];
if (cur < 45) Z.x[j].first += (1LL << cur);
else Z.x[j].second += (1LL << (cur - 45));
}
}
// Step 3. Find Min
int Minv = 0;
for (int i = 1; i <= 10; i++) {
pair<bool, int> ret = Solve(i, 0, Z);
if (ret.first == true) { Minv = i; break; }
}
cout << Minv << endl;
// Step 3. Interaction
for (int loops = Minv; loops >= 1; loops--) {
pair<bool, int> ret = Solve(loops, 0, Z);
cout << "? " << ret.second / 9 << " " << ret.second % 9 << endl;
int x; cin >> x;
x++;
Z = Apply(Z, ret.second, x);
vector<int> cand;
if (Z.x[0] != make_pair(0LL, 0LL)) cand.push_back(0);
if (Z.x[1] != make_pair(0LL, 0LL)) cand.push_back(1);
if (Z.x[2] != make_pair(0LL, 0LL)) cand.push_back(2);
if (Z.x[3] != make_pair(0LL, 0LL)) cand.push_back(3);
if (Z.x[4] != make_pair(0LL, 0LL)) cand.push_back(4);
if (Z.x[5] != make_pair(0LL, 0LL)) cand.push_back(5);
if (cand.size() == 1) {
char role[7] = "JSCMXB";
cout << "! " << role[cand[0]] << endl;
return 0;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3916kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 2ms
memory: 4256kb
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: 2ms
memory: 4260kb
input:
1 2 4 -1 1
output:
2 ? 0 0 ? 0 2 ! X
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 2ms
memory: 4056kb
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: 2ms
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: 2ms
memory: 3920kb
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: 2ms
memory: 3864kb
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: 2ms
memory: 4264kb
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: 2ms
memory: 3952kb
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: -100
Wrong Answer
time: 0ms
memory: 3964kb
input:
10 4 0 0 0 5 0 7 0 8 0 1 0 6 0 9 0 2 0 3 0
output:
3 ? 0 0
result:
wrong answer solution think m=3, while jury think m=2.