QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#707853 | #9537. Chinese Chess | ucup-team173 | WA | 9ms | 4364kb | C++20 | 6.2kb | 2024-11-03 17:50:34 | 2024-11-03 17:50:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define mpr make_pair
#define pb push_back
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;
int flg = 1;
vector<pair<int, int>> ve;
ve.push_back({0, 4}), ve.push_back({5, 4}), ve.push_back({8, 4}), ve.push_back({2, 4});
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
if (i < ve.size() && ve[i] != make_pair(x, y)) flg = 0;
for (int j = 0; j < 6; j++) {
A.push_back({x, y, j});
}
}
using T = unordered_map<int, vector<array<int, 3>>>;
auto get = [&](int i, int j, const vector<array<int, 3>> &A) {
T res;
for (auto [x, y, ty] : A) {
res[f[x][y][ty][i][j]].push_back({x, y, ty});
}
return res;
};
auto evalv = [&](const vector<array<int, 3>> &v) -> pair<int, int> {
int sz = v.size();
set<int> tys;
for (auto [x, y, ty] : v) tys.insert(ty);
return {(int)tys.size(), sz};
};
auto eval = [&](const T &mp) -> pair<int, int> {
if (mp.size() == 0) return {1e9, 1e9};
pair<int, int> mx = {-1, -1};
for (auto [k, v] : mp) {
mx = max(mx, evalv(v));
}
return mx;
};
int m = 0;
int lim = 1000;
vector<vector<array<int, 3>>> states = {A};
vector<pair<pair<int,int>,vector<array<int, 3>>>>new_states;
while (1) {
m++;
new_states.clear();
for (auto AA : states) {
T mp;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 9; j++) {
mp = get(i, j, AA);
vector<array<int, 3>> BB;
pair<int, int> val = {-1, -1};
for (auto [k, v] : mp) {
if (evalv(v) > val) {
val = evalv(v);
BB = v;
}
}
set<int> tys;
for (auto [x, y, ty] : BB) tys.insert(ty);
if (tys.size() == 1) {
// cout << "! " << ans[*tys.begin()] << endl;
goto fuck;
}
new_states.pb(mpr(val,BB));
}
}
}
sort(new_states.begin(),new_states.end());
reverse(new_states.begin(),new_states.end());
if(new_states.size()>lim){
new_states.resize(lim);
}
states.clear();
for(auto [a,b]:new_states){
states.pb(b);
}
}
fuck:;
cout << m << endl;
while (1) {
T mp = get(0, 0, A);
int qx = 0, qy = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 9; j++) {
auto now = get(i, j, A);
if (eval(mp) > eval(now)) {
mp = now;
qx = i, qy = j;
}
}
}
cout << "? " << qx << ' ' << qy << endl;
int res;
cin >> res;
if (flg) {
for (auto [k, v] : mp) {
cout << k << endl;
for (auto [x, y, ty] : v) {
cout << " " << x << ' ' << y << ' ' << ty << endl;
}
}
cout << "res: " << res << endl;
return;
}
assert(mp[res].size() > 0);
// assert(A != mp[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: 100
Accepted
time: 8ms
memory: 4132kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 9ms
memory: 4328kb
input:
4 2 1 2 3 2 5 2 7 12 9
output:
2 ? 7 0 ? 0 0 ! J
result:
ok number is guessed.
Test #3:
score: 0
Accepted
time: 8ms
memory: 4016kb
input:
1 2 4 -1 1
output:
2 ? 0 0 ? 0 2 ! X
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 8ms
memory: 4064kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 8ms
memory: 4064kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 4ms
memory: 4364kb
input:
2 7 7 1 0 5 14
output:
2 ? 7 2 ? 0 0 ! J
result:
ok number is guessed.
Test #7:
score: 0
Accepted
time: 3ms
memory: 4068kb
input:
5 8 6 1 3 0 5 2 4 0 2 11 6
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #8:
score: 0
Accepted
time: 6ms
memory: 4068kb
input:
6 0 7 1 6 2 8 0 5 7 6 8 2 11 -1
output:
2 ? 9 7 ? 0 0 ! B
result:
ok number is guessed.
Test #9:
score: 0
Accepted
time: 5ms
memory: 4064kb
input:
7 6 5 3 0 3 2 4 1 4 0 2 4 5 2 9 3
output:
2 ? 6 6 ? 0 0 ! J
result:
ok number is guessed.
Test #10:
score: 0
Accepted
time: 9ms
memory: 4128kb
input:
8 3 3 2 5 6 2 7 4 1 4 3 0 2 4 3 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #11:
score: 0
Accepted
time: 9ms
memory: 4136kb
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8 8 9
output:
2 ? 7 4 ? 0 0 ! J
result:
ok number is guessed.
Test #12:
score: 0
Accepted
time: 8ms
memory: 3852kb
input:
10 4 0 0 0 5 0 7 0 8 0 1 0 6 0 9 0 2 0 3 0 16 -1
output:
2 ? 9 7 ? 0 1 ! B
result:
ok number is guessed.
Test #13:
score: 0
Accepted
time: 8ms
memory: 4124kb
input:
9 1 8 1 2 1 5 1 6 1 3 1 4 1 0 1 1 1 7 8 8
output:
2 ? 6 4 ? 0 0 ! J
result:
ok number is guessed.
Test #14:
score: -100
Wrong Answer
time: 9ms
memory: 4068kb
input:
10 0 4 5 4 8 4 2 4 4 4 7 4 3 4 9 4 6 4 1 4 -1
output:
2 ? 4 0 9 9 4 0 7 7 4 0 1 4 0 1 4 4 2 6 2 4 0 6 4 0 3 5 4 3 7 4 3 3 4 3 9 4 3 1 4 3 5 5 4 0 3 4 0 -1 0 4 5 5 4 1 5 4 4 5 4 5 8 4 5 2 4 4 2 4 5 4 4 5 7 4 1 7 4 4 7 4 5 3 4 1 3 4 4 3 4 5 9 4 1 9 4 4 9 4 5 6 4 ...
result:
wrong answer Token "9" doesn't correspond to pattern "!|?"