QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#764173#9537. Chinese ChessjakerWA 2ms3872kbC++205.0kb2024-11-20 02:56:332024-11-20 02:56:35

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 02:56:35]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3872kb
  • [2024-11-20 02:56:33]
  • 提交

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)