QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#764173 | #9537. Chinese Chess | jaker | WA | 2ms | 3872kb | C++20 | 5.0kb | 2024-11-20 02:56:33 | 2024-11-20 02:56:35 |
Judging History
answer
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define f(i,j,k) dir[i].pb(mp(j,k))
#define ll long long
#define pb push_back
#define mp make_pair
#define y1 Y1
int n,m,mx_dep,mx_dis;
struct node {
int x,y,tp;
}a[10000];
int dis[6][10][10][10][10];
vector< pair<int,int> > dir[10];
void pre() {
dir[0].pb(mp(1,0)); dir[0].pb(mp(-1,0)); dir[0].pb(mp(0,1)); dir[0].pb(mp(0,-1));
dir[1].pb(mp(1,1)); dir[1].pb(mp(1,-1)); dir[1].pb(mp(-1,1)); dir[1].pb(mp(-1,-1));
rep(i,1,9) dir[2].pb( mp( i , 0 ) ) , dir[2].pb( mp( -i , 0 ) );
rep(i,1,8) dir[2].pb( mp( 0 , i ) ) , dir[2].pb( mp( 0 , -i ) );
f(3,2,1); f(3,2,-1); f(3,-2,1); f(3,-2,-1);
f(3,1,2); f(3,1,-2); f(3,-1,2); f(3,-1,-2);
f(4,2,2); f(4,2,-2); f(4,-2,2); f(4,-2,-2);
f(5,1,0); f(5,0,1); f(5,0,-1); f(6,1,0);
rep(tp,0,5) rep(x,0,9) rep(y,0,8) {
rep(x1,0,9) rep(y1,0,8) dis[tp][x][y][x1][y1] = 10000;
dis[tp][x][y][x][y] = 0;
queue<pair<int,int>>q; q.push(mp(x,y));
while(!q.empty()) {
auto [x1,y1] = q.front(); q.pop();
int t = (tp==5&&x1<=4)?6:tp;
for(auto [dx,dy]:dir[t]) {
int nx = x1 + dx , ny = y1 + dy;
if( dis[tp][x][y][nx][ny] == 10000 )
dis[tp][x][y][nx][ny] = dis[tp][x][y][x1][y1] + 1 , q.push( mp( nx , ny ) );
}
}
}
rep(tp,0,5) rep(x,0,9) rep(y,0,8)
rep(x1,0,9) rep(y1,0,8)
if( dis[tp][x][y][x1][y1] != 10000 )
mx_dis = max( mx_dis , dis[tp][x][y][x1][y1] );
rep(tp,0,5) rep(x,0,9) rep(y,0,8)
rep(x1,0,9) rep(y1,0,8)
if( dis[tp][x][y][x1][y1] == 10000 )
dis[tp][x][y][x1][y1] = mx_dis + 1;
mx_dis++;
}
void output(int x) {
cout << x << endl;
fflush(stdout);
}
vector<int>dis_id[10][25];
int dfs(const vector<int> &pos,int dep) {
bool vis[7] = {}; int cnt = 0;
for( auto x : pos ) if(!vis[a[x].tp]) vis[a[x].tp] = true , ++cnt;
if( cnt == 1 ) return dep - 1;
if( dep == mx_dep + 1 ) return dep;
int mn = mx_dep + 1;
pair<int,int>best;
rep(x1,0,9) rep(y1,0,8) {
rep(DIS,0,mx_dis) dis_id[dep][DIS].clear();
for( auto id : pos ) {
int tp = a[id].tp , x = a[id].x , y = a[id].y;
dis_id[dep][ dis[tp][x][y][x1][y1] ].pb( id );
}
int mx = 0;
rep(DIS,0,mx_dis) if( !dis_id[dep][DIS].empty() ) {
if( (int)(dis_id[dep][DIS].size()) == (int)(pos.size()) )
mx = mx_dep + 1;
else
mx = max( mx , dfs( dis_id[dep][DIS] , dep + 1 ) );
if( mx >= mn ) break;
}
if( mx < mn ) mn = mx , best = mp( x1 , y1 );
}
return mn;
}
void solve(vector<int> pos,int dep) {
// printf("#%d\n",dep);
// for( auto x : pos ) {
// printf("%d %d %d\n",a[x].tp,a[x].x,a[x].y);
// }
bool vis[7] = {}; int cnt = 0;
for( auto x : pos ) if(!vis[a[x].tp]) vis[a[x].tp] = true , ++cnt;
if( cnt == 1 && dep == mx_dep + 1 ) {
if( a[pos[0]].tp == 0 ) cout << "! J" << endl;
else if( a[pos[0]].tp == 1 ) cout << "! S" << endl;
else if( a[pos[0]].tp == 2 ) cout << "! C" << endl;
else if( a[pos[0]].tp == 3 ) cout << "! M" << endl;
else if( a[pos[0]].tp == 4 ) cout << "! X" << endl;
else if( a[pos[0]].tp == 5 ) cout << "! B" << endl;
return;
}
if( cnt == 1 || dep == mx_dep + 1 )
assert(0);
int mn = mx_dep + 1;
pair<int,int>best;
rep(x1,0,9) rep(y1,0,8) {
rep(DIS,0,mx_dis) dis_id[dep][DIS].clear();
for( auto id : pos ) {
int tp = a[id].tp , x = a[id].x , y = a[id].y;
dis_id[dep][ dis[tp][x][y][x1][y1] ].pb( id );
}
int mx = 0;
rep(DIS,0,mx_dis) if( !dis_id[dep][DIS].empty() ) {
if( (int)(dis_id[dep][DIS].size()) == (int)(pos.size()) )
mx = mx_dep + 1;
else
mx = max( mx , dfs( dis_id[dep][DIS] , dep + 1 ) );
if( mx >= mn ) break;
}
if( mx < mn ) mn = mx , best = mp( x1 , y1 );
}
cout << "? " << best.first << " " << best.second << endl;
fflush(stdout);
int DIS; cin >> DIS;
if( DIS == -1 ) DIS = mx_dis;
auto [x1,y1] = best;
dis_id[dep][DIS].clear();
for( auto id : pos ) {
int tp = a[id].tp , x = a[id].x , y = a[id].y;
if( dis[tp][x][y][x1][y1] == DIS )
dis_id[dep][DIS].pb(id);
}
solve( dis_id[dep][DIS] , dep + 1 );
}
int main() {
cin >> n;
rep(i,1,n) {
int x,y; cin >> x >> y;
rep(j,0,5) a[++m] = (node){x,y,j};
}
pre();
vector<int>st; rep(i,1,m) st.pb(i);
for(mx_dep=1;mx_dep<=5;++mx_dep)
if( dfs(st,1) == mx_dep ) break;
output(mx_dep);
solve(st,1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3872kb
input:
1 9 0 -1
output:
1 ? 0 2 ! B
result:
wrong answer correct but in a random way.(9 0 5)