QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#834845 | #9537. Chinese Chess | Ballmer Peak (Ali Safari, AmirMohammad Shahrezaei, Alireza Keshavarz) | TL | 475ms | 4492kb | C++17 | 3.8kb | 2024-12-28 04:28:22 | 2024-12-28 04:28:22 |
Judging History
answer
#ifdef safar
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <numeric>
#else
#include <bits/stdc++.h>
#endif
#define rep(i, a, b) for(int i = a; i < (b); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef bitset<540> bt;
const int N = 100 + 10;
const int Sq = 4e4;
string names = "JSCMXB";
int id[N][N];
int dis[6][N][N];
bt val[N][N]; // dis pos
int tot = 90;
int n = 10, m = 9;
int pc = 6;
int bst = 4;
unordered_map<bt, pii> mem;
inline int OK(int x){
return (x + N) % N;
}
pair<int, int> Solve(bt cur, int dep){
if(mem.count(cur))
return mem[cur];
set<int> st;
rep(i, 0, 6 * tot) if(cur[i]) st.insert(i % 6);
if(st.size() <= 1) return {0, -1};
if(dep == bst) return {20, -1};
int mv = -1;
int rq = 10;
rep(q, 0, tot){
set<int> pd;
rep(i, 0, 6 * tot) if(cur[i]) pd.insert(OK(dis[i % 6][i / 6][q]));
int cst = 1;
for(auto ds : pd) cst = max(cst, 1 + Solve(cur & val[ds][q], dep + 1).F);
if(cst <= rq){
rq = cst;
mv = q;
}
if(cst >= rq) continue;
}
return mem[cur] = {rq, mv};
}
bt cur;
int Main(){
rep(i, 0, 10) rep(j, 0, 9) id[i][j] = i * 9 + j;
memset(dis, 31, sizeof dis);
rep(t, 0, 6){
rep(i, 0, n){
rep(j, 0, m){
vector<pii> dlt;
if(t == 0) dlt = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
if(t == 1) dlt = {{1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
if(t == 2){
rep(i, 1, 11) dlt.pb({0, i});
rep(i, 1, 11) dlt.pb({0, -i});
rep(i, 1, 11) dlt.pb({-i, 0});
rep(i, 1, 11) dlt.pb({i, 0});
}
if(t == 3) dlt = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
if(t == 4) dlt = {{2, -2}, {-2, 2}, {2, 2}, {-2, -2}};
if(t == 5 && i <= 4) dlt = {{1, 0}};
if(t == 5 && i > 4) dlt = {{1, 0}, {0, 1}, {0, -1}};
for(auto [dx, dy] : dlt){
int nx = dx + i;
int ny = dy + j;
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
dis[t][id[i][j]][id[nx][ny]] = 1;
}
}
}
rep(md, 0, tot)rep(u, 0, tot) rep(v, 0, tot){
dis[t][u][v] = min(dis[t][u][v], dis[t][u][md] + dis[t][md][v]);
}
rep(u, 0, tot) rep(v, 0, tot) if(dis[t][u][v] > tot) dis[t][u][v] = -1;
rep(u, 0, tot) rep(v, 0, tot) val[OK(dis[t][u][v])][v][u * 6 + t] = 1;
}
vector<pii> sts, tmp;
// vector<int> Q = {0, 1, tot - 2, tot - 1};
// map<vector<int>, vector<pii> > mp;
// for(auto st : sts){
// vector<int> X;
// for(auto q : Q) X.pb(dis[st.F][st.S][q]);
// mp[X].pb(st);
// }
// for(auto el : mp){
// set<int> tmp;
// for(auto [p, pos] : el.S) tmp.insert(p);
// // cerr << el.S.size() << ' ' << tmp.size() << '\n';
// if(tmp.size() > 1){
// for(auto [p, pos] : el.S) cerr << p << " at (" << pos/m << " , " << pos % m << ")\n";
// cerr << "# ";
// for(auto x : el.F) cerr << x << ' '; cerr << '\n';
// cerr << '\n';
// }
// }
int k;
cin >> k;
rep(i, 0, k){
int pos, x, y;
cin >> x >> y;
pos = x * m + y;
rep(p, 0, 6) cur[pos * 6 + p] = 1;
}
auto slv = Solve(cur, 0);
cout << slv.F << '\n';
while(true){
set<int> st;
rep(i, 0, 6 * tot) if(cur[i]) st.insert(i % 6);
if(st.size() <= 1){
cout << "! " << names[*st.begin()] << endl;
break;
}
auto slv = Solve(cur, 0);
cout << "? " << slv.S / m << ' ' << slv.S % m << endl;
int res;
cin >> res;
cur &= val[OK(res)][slv.S];
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
int tc = 1;
// cin >> tc;
while(tc --) Main();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 11ms
memory: 4068kb
input:
1 9 0 6
output:
1 ? 7 6 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 85ms
memory: 4044kb
input:
4 2 1 2 3 2 5 2 7 14 -1
output:
2 ? 9 8 ? 4 8 ! B
result:
ok number is guessed.
Test #3:
score: 0
Accepted
time: 12ms
memory: 4108kb
input:
1 2 4 -1 7
output:
2 ? 9 8 ? 9 7 ! S
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 9ms
memory: 4232kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 13ms
memory: 3948kb
input:
1 6 0 6
output:
1 ? 4 6 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 23ms
memory: 4048kb
input:
2 7 7 1 0 16 -1
output:
2 ? 9 8 ? 4 8 ! B
result:
ok number is guessed.
Test #7:
score: 0
Accepted
time: 172ms
memory: 4312kb
input:
5 8 6 1 3 0 5 2 4 0 2 13 8
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #8:
score: 0
Accepted
time: 241ms
memory: 4328kb
input:
6 0 7 1 6 2 8 0 5 7 6 8 2 12 7
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #9:
score: 0
Accepted
time: 380ms
memory: 4216kb
input:
7 6 5 3 0 3 2 4 1 4 0 2 4 5 2 13 8
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #10:
score: 0
Accepted
time: 475ms
memory: 4304kb
input:
8 3 3 2 5 6 2 7 4 1 4 3 0 2 4 3 4 12 7
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #11:
score: 0
Accepted
time: 318ms
memory: 4200kb
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8 15 10
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #12:
score: 0
Accepted
time: 405ms
memory: 4216kb
input:
10 4 0 0 0 5 0 7 0 8 0 1 0 6 0 9 0 2 0 3 0 16 11
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #13:
score: 0
Accepted
time: 300ms
memory: 4424kb
input:
9 1 8 1 2 1 5 1 6 1 3 1 4 1 0 1 1 1 7 16 -1
output:
2 ? 9 8 ? 4 8 ! B
result:
ok number is guessed.
Test #14:
score: 0
Accepted
time: 322ms
memory: 4164kb
input:
10 0 4 5 4 8 4 2 4 4 4 7 4 3 4 9 4 6 4 1 4 11 7
output:
2 ? 9 7 ? 4 8 ! J
result:
ok number is guessed.
Test #15:
score: 0
Accepted
time: 340ms
memory: 4228kb
input:
9 4 6 4 5 4 7 4 4 4 1 4 3 4 0 4 8 4 2 13 8
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #16:
score: 0
Accepted
time: 382ms
memory: 4492kb
input:
10 9 2 5 2 1 2 8 2 6 2 7 2 2 2 0 2 4 2 3 2 14 9
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #17:
score: 0
Accepted
time: 318ms
memory: 4244kb
input:
9 3 1 3 7 3 5 3 3 3 6 3 4 3 0 3 2 3 8 14 -1
output:
2 ? 9 8 ? 4 8 ! B
result:
ok number is guessed.
Test #18:
score: 0
Accepted
time: 389ms
memory: 4208kb
input:
10 5 1 8 1 6 1 4 1 3 1 0 1 2 1 7 1 9 1 1 1 16 -1
output:
2 ? 9 8 ? 4 8 ! B
result:
ok number is guessed.
Test #19:
score: 0
Accepted
time: 299ms
memory: 4264kb
input:
9 1 6 1 4 1 3 1 7 1 8 1 5 1 2 1 1 1 0 16 -1
output:
2 ? 9 8 ? 4 8 ! B
result:
ok number is guessed.
Test #20:
score: 0
Accepted
time: 405ms
memory: 4208kb
input:
10 5 0 9 0 1 0 2 0 3 0 6 0 7 0 4 0 0 0 8 0 16 11
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #21:
score: 0
Accepted
time: 360ms
memory: 4208kb
input:
9 0 3 0 5 0 7 0 0 0 4 0 8 0 1 0 6 0 2 17 12
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #22:
score: 0
Accepted
time: 402ms
memory: 4248kb
input:
10 1 0 9 0 4 0 2 0 8 0 7 0 5 0 3 0 0 0 6 0 16 11
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #23:
score: 0
Accepted
time: 298ms
memory: 4160kb
input:
9 1 8 1 2 1 7 1 0 1 4 1 6 1 1 1 5 1 3 16 -1
output:
2 ? 9 8 ? 4 8 ! B
result:
ok number is guessed.
Test #24:
score: 0
Accepted
time: 324ms
memory: 4120kb
input:
10 2 4 1 4 0 4 6 4 4 4 9 4 5 4 3 4 7 4 8 4 11 7
output:
2 ? 9 7 ? 4 8 ! J
result:
ok number is guessed.
Test #25:
score: 0
Accepted
time: 362ms
memory: 4240kb
input:
9 0 2 0 7 0 5 0 4 0 0 0 3 0 1 0 6 0 8 17 12
output:
2 ? 9 8 ? 4 8 ! J
result:
ok number is guessed.
Test #26:
score: 0
Accepted
time: 341ms
memory: 4184kb
input:
10 5 3 2 3 3 3 8 3 9 3 1 3 6 3 7 3 0 3 4 3 14 -1
output:
2 ? 9 8 ? 4 8 ! B
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 3 2 3
output:
3 ? 9 8 ? 9 7 ? 7 2 ! M