QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711447#9537. Chinese ChessshmilycWA 1ms4200kbC++2316.1kb2024-11-05 11:06:342024-11-05 11:06:35

Judging History

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

  • [2024-11-05 11:06:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4200kb
  • [2024-11-05 11:06:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=11;
#define int long long
#define mp make_pair

struct Point
{
    int r;
    int c;
    int pos;
    Point(){}
    Point(int _r,int _c,int _pos){
        r=_r;c=_c;pos=_pos;
    }
};
int S[N][N][N][N],C[N][N][N][N],M[N][N][N][N],X[N][N][N][N],B[N][N][N][N];
int lenJ(int r,int c,int x,int y)
{
    return fabs(r-x)+fabs(c-y);
}

int lenS(int r,int c,int x,int y)
{
    if(r==x&&c==y)
        return 0;
    if(S[r][c][x][y]||S[x][y][r][c])
        return S[r][c][x][y];
    queue<Point> q;
    q.push(Point(r,c,0));
    int vis[10][10];
    memset(vis,-1,sizeof(vis));
    vis[r][c]=0;
    int dx[4]={1,1,-1,-1};
    int dy[4]={1,-1,1,-1};
    while(!q.empty()){
        int nx=q.front().r,ny=q.front().c;
        int pos=q.front().pos;
        q.pop();
        for(int i=0;i<4;i++){
            if(nx+dx[i]<0||nx+dx[i]>9||ny+dy[i]<0||ny+dy[i]>8||vis[nx+dx[i]][ny+dy[i]]!=-1)
                continue;
            S[r][c][nx+dx[i]][ny+dy[i]]=pos+1;
            S[nx+dx[i]][ny+dy[i]][r][c]=pos+1;
            vis[nx+dx[i]][ny+dy[i]]=pos+1;
            q.push(Point(nx+dx[i],ny+dy[i],pos+1));
        }
    }
    for(int i=0;i<=9;i++)
        for(int j=0;j<=8;j++){
            S[i][j][r][c]=vis[i][j];
            S[r][c][i][j]=vis[i][j];
        }
    return vis[x][y];
}

int lenC(int r,int c,int x,int y)
{
    if(r==x&&c==y)
        return 0;
    else if(r!=x&&c!=y)
        return 2;
    else
        return 1;
}

int lenM(int r,int c,int x,int y)
{
    if(r==x&&c==y)
        return 0;
    if(M[r][c][x][y]||M[x][y][r][c])
        return M[r][c][x][y];
    queue<Point> q;
    q.push(Point(r,c,0));
    int vis[10][10];
    memset(vis,-1,sizeof(vis));
    vis[r][c]=0;
    int dx[8]={2,2,-2,-2,1,1,-1,-1};
    int dy[8]={1,-1,1,-1,2,-2,2,-2};
    while(!q.empty()){
        int nx=q.front().r,ny=q.front().c;
        int pos=q.front().pos;
        q.pop();
        for(int i=0;i<8;i++){
            if(nx+dx[i]<0||nx+dx[i]>9||ny+dy[i]<0||ny+dy[i]>8||vis[nx+dx[i]][ny+dy[i]]!=-1)
                continue;
            M[r][c][nx+dx[i]][ny+dy[i]]=pos+1;
            M[nx+dx[i]][ny+dy[i]][r][r]=pos+1;
            vis[nx+dx[i]][ny+dy[i]]=pos+1;
            q.push(Point(nx+dx[i],ny+dy[i],pos+1));
            // if(nx+dx[i]==0&&ny+dy[i]==0){
            //     cout<<nx<<' '<<ny<<' '<<pos<<endl;
            // }
            // if(nx+dx[i]==1&&ny+dy[i]==2){
            //     cout<<nx<<' '<<ny<<' '<<pos<<endl;
            // }
        }
    }
    for(int i=0;i<=9;i++)
        for(int j=0;j<=8;j++){
            M[i][j][r][c]=vis[i][j];
            M[r][c][i][j]=vis[i][j];
        }
    return vis[x][y];
}

int lenX(int r,int c,int x,int y)
{
    if(r==x&&c==y)
        return 0;
    if(X[r][c][x][y]||X[x][y][r][c])
        return X[r][c][x][y];
    queue<Point> q;
    q.push(Point(r,c,0));
    int vis[10][10];
    memset(vis,-1,sizeof(vis));
    vis[r][c]=0;
    int dx[4]={2,2,-2,-2};
    int dy[4]={2,-2,2,-2};
    while(!q.empty()){
        int nx=q.front().r,ny=q.front().c;
        int pos=q.front().pos;
        q.pop();
        for(int i=0;i<4;i++){
            if(nx+dx[i]<0||nx+dx[i]>9||ny+dy[i]<0||ny+dy[i]>8||vis[nx+dx[i]][ny+dy[i]]!=-1)
                continue;
            X[nx+dx[i]][ny+dy[i]][r][c]=pos+1;
            X[r][c][nx+dx[i]][ny+dy[i]]=pos+1;
            vis[nx+dx[i]][ny+dy[i]]=pos+1;
            q.push(Point(nx+dx[i],ny+dy[i],pos+1));
        }
    }
    for(int i=0;i<=9;i++)
        for(int j=0;j<=8;j++){
            X[i][j][r][c]=vis[i][j];
            X[r][c][i][j]=vis[i][j];
        }
    return vis[x][y];
}

int lenB(int x,int y,int r,int c)//r c->x y
{
    if(x==r&&y==c)
        return 0;
    if(B[r][c][x][y])
        return B[r][c][x][y];
    queue<Point> q;
    q.push(Point(r,c,0));
    int vis[10][10];
    memset(vis,-1,sizeof(vis));
    vis[r][c]=0;
    int dx[4]={1,1,0,0};
    int dy[4]={0,0,1,-1};
    while(!q.empty()){
        int nx=q.front().r,ny=q.front().c;
        int pos=q.front().pos;
        q.pop();
        for(int i=0;i<4;i++){
            if(nx+dx[i]<0||nx+dx[i]>9||ny+dy[i]<0||ny+dy[i]>8||vis[nx+dx[i]][ny+dy[i]]!=-1)
                continue;
            if(nx<=4&&i)
                continue;
            B[r][c][nx+dx[i]][ny+dy[i]]=pos+1;
            vis[nx+dx[i]][ny+dy[i]]=pos+1;
            q.push(Point(nx+dx[i],ny+dy[i],pos+1));
        }
    }
    for(int i=0;i<=9;i++)
        for(int j=0;j<=8;j++)
            B[r][c][i][j]=vis[i][j];
    return vis[x][y];
}

void ask(int a,int b,int &len)
{
    cout<<"? "<<a<<' '<<b<<endl;
    cout.flush();
    cin>>len;
    return;
}

void print(int a)
{
    char c[8]={' ','J','S','C','M','X','B'};
    cout<<"! "<<c[a]<<endl;
    cout.flush();
}

void solve()
{
    // cout<<lenM(2,7,0,0)<<endl;
    // return;
    // init();
    int n;
    cin>>n;
    vector<Point> a;
    for(int i=1,x,y;i<=n;i++){
        cin>>x>>y;
        a.push_back(Point(x,y,0));
    }
    //一次检测出现结果是,存在一个点,所有种类的棋子都能被区分掉,一个棋子不会出现两种到达路线
    vector<vector<int> >best;
    for(int r=0;r<=9;r++){
        for(int c=0;c<=8;c++){
            int len[7]={0,100,100,100,100,100,100};
            bool flag=true;
            //存储所有起点到当前问询的距离,如果每一个距离都对应一个棋子才可以一次问询解决
            for(int i=0;i<a.size()&&flag;i++){
                int x=a[i].r;
                int y=a[i].c;
                int temp=lenJ(r,c,x,y);
                if(len[1]==100)
                    len[1]=temp;
                else if(len[1]!=temp)
                    flag=false;
                temp=lenS(r,c,x,y);
                if(len[2]==100)
                    len[2]=temp;
                else if(len[2]!=temp)
                    flag=false;
                temp=lenC(r,c,x,y);
                if(len[3]==100)
                    len[3]=temp;
                else if(len[3]!=temp)
                    flag=false;
                temp=lenM(r,c,x,y);
                if(len[4]==100)
                    len[4]=temp;
                else if(len[4]!=temp)
                    flag=false;
                temp=lenX(r,c,x,y);
                if(len[5]==100)
                    len[5]=temp;
                else if(len[5]!=temp)
                    flag=false;
                temp=lenB(r,c,x,y);
                if(len[6]==100)
                    len[6]=temp;
                else if(len[6]!=temp)
                    flag=false;
            }
            for(int i=1;i<=6;i++)
                for(int j=i+1;j<=6;j++)
                    if(len[i]==len[j])
                        flag=false;
            if(flag==true){//一次问询结果
                cout<<1<<endl;
                cout.flush();
                int l;
                ask(r,c,l);
                for(int i=1;i<=6;i++)
                    if(l==len[i]){
                        print(i);
                        break;
                    }
                return;
            }
        }
    }
    // return;
    if(n<50){
        //两次查询能查结束,说明对每一种棋子,在所有输入点中,只存在一种可能情况
        for(int r1=0;r1<=0;r1++)
            for(int c1=0;c1<=0;c1++){
                //对于第一次这个点的问询,存在通过改变第二个点的问询结果来使得,可以得到更优的解法
                map<int,vector<Point>> m1;//存储第一次问询的距离点可能
                map<int,pair<int,int> > ans;
                for(int i=0;i<a.size();i++){
                    int x=a[i].r;
                    int y=a[i].c;
                    m1[lenJ(r1,c1,x,y)].push_back(Point(x,y,1));
                    m1[lenS(r1,c1,x,y)].push_back(Point(x,y,2));
                    m1[lenC(r1,c1,x,y)].push_back(Point(x,y,3));
                    m1[lenM(r1,c1,x,y)].push_back(Point(x,y,4));
                    m1[lenX(r1,c1,x,y)].push_back(Point(x,y,5));
                    m1[lenB(r1,c1,x,y)].push_back(Point(x,y,6));
                }//存储问询结果
                //需要所有距离都有对应的点才是true;
                bool flag=true;
                for(auto temp1:m1){
                    if(flag==false)
                        break;
                    //对于每个距离进行问询,找到一个合适的第二次问询来分类,对于每一个距离都会存在一个最好的第二次问询
                    bool findif=true;//用来标记是否找到第二个点,默认没找到
                    for(int r2=0;r2<=9&&findif;r2++)
                        for(int c2=0;c2<=8&&findif;c2++){
                            if(r1==r2&&c1==c2)
                                continue;
                            bool check2=true;//用来标记当前找到的第二次查询是否符合条件,默认符合
                            map<int,vector<Point>> m2;
                            for(int i=0;i<a.size();i++){
                                int x=a[i].r;
                                int y=a[i].c;
                                m2[lenJ(r2,c2,x,y)].push_back(Point(x,y,1));
                                m2[lenS(r2,c2,x,y)].push_back(Point(x,y,2));
                                m2[lenC(r2,c2,x,y)].push_back(Point(x,y,3));
                                m2[lenM(r2,c2,x,y)].push_back(Point(x,y,4));
                                m2[lenX(r2,c2,x,y)].push_back(Point(x,y,5));
                                m2[lenB(r2,c2,x,y)].push_back(Point(x,y,6));
                            }
                            //统计第二次问询的所有点所产生的距离
                            //判断对于这个距离,第二次问询所选择的点是否合适
                            for(auto temp2:m2){//第二次查询
                                //对于所有第一次查询出的距离和第二次查询出的距离
                                int check[7]={0};//判断这种返回情况是否属实
                                int cnt=0;
                                // int R,C;
                                //temp.first 返回的距离,temp.second为满足这个距离还需要区分的种类
                                for(int q=0;q<temp1.second.size()&&flag;q++)
                                    for(int p=0;p<temp2.second.size();p++){
                                        if(temp1.second[q].c==temp2.second[p].c
                                            &&temp1.second[q].r==temp2.second[p].r
                                            &&temp1.second[q].pos==temp2.second[p].pos
                                            // &&(cnt==0||temp1.second[q].c==C&&temp1.second[q].r==R)
                                        ){//属于同一种情况
                                            if(check[temp1.second[q].pos]==0){
                                                // if(temp1.first==9&&temp2.first==2){
                                                //     cout<<temp1.second[q].c<<' '<<temp1.second[q].r<<' ';
                                                //     cout<<temp1.second[q].pos<<endl;
                                                // }
                                                check[temp1.second[q].pos]=1;
                                                cnt++;
                                                // if(cnt==1){
                                                //     C=temp1.second[q].c;
                                                //     R=temp1.second[q].r;
                                                // }
                                                if(cnt==2){
                                                    // flag=false;
                                                    check2=false;
                                                    // cout<<"?"<<temp1.first<<" "<<temp2.first<<" "<<cnt<<endl;
                                                    break;
                                                }
                                            }
                                        }
                                    }
                                if(check2==false)
                                    break;
                            }
                            if(check2){//这次的符合结果
                                findif=false;
                                ans[temp1.first]=make_pair(r2,c2);
// cout<<temp1.first<<'<'<<r2<<' '<<c2<<' '<<"++++"<<endl;
                                break;
                            }
                        }
                    if(findif){//对于这个距离没有合适的第二次查询
                        flag=false;
                    }
                }
// cout<<">>>"<<flag<<endl;
// cout<<ans[5].first<<' '<<ans[5].second<<endl;
                if(flag==true){//这两个点满足两次问询得到答案
                    // return;
                    int len1,len2;
                    cout<<2<<endl;
                    cout.flush();
                    ask(r1,c1,len1);
                    int r2=ans[len1].first;int c2=ans[len1].second;
                    ask(r2,c2,len2);
                    // cout<<lenM(2,7,0,0)<<' '<<lenM(2,7,0,6)<<endl;
                    // cout<<len1<<' '<<len2<<endl;
                    for(int i=0;i<a.size();i++){
                        int r=a[i].r;int c=a[i].c;
                        // cout<<r<<' '<<c<<endl;
                        if(len1==lenJ(r,c,r1,c1)&&len2==lenJ(r,c,r2,c2)){
                            print(1);
                            return;
                        }
                        if(len1==lenS(r,c,r1,c1)&&len2==lenS(r,c,r2,c2)){
                            print(2);
                            return;
                        }
                        if(len1==lenC(r,c,r1,c1)&&len2==lenC(r,c,r2,c2)){
                            print(3);
                            return;
                        }
                        if(len1==lenM(r,c,r1,c1)&&len2==lenM(r,c,r2,c2)){
                            print(4);
                            return;
                        }
                        if(len1==lenX(r,c,r1,c1)&&len2==lenX(r,c,r2,c2)){
                            print(5);
                            return;
                        }
                        if(len1==lenB(r1,c1,r,c)&&len2==lenB(r2,c2,r,c)){
                            print(6);
                            return;
                        }
                    }
                }
            }
    }
    // cout<<"errror\n";
    // return;
    //三次查询处
    cout<<3<<endl;
    cout.flush();
    int len1,len2,len3;
    ask(0,0,len1);
    ask(8,0,len2);
    ask(1,5,len3);
    for(int i=0;i<a.size();i++){
        int x=a[i].r;
        int y=a[i].c;
        if(len1==lenJ(0,0,x,y)&&len2==lenJ(8,0,x,y)&&len3==lenJ(1,5,x,y)){
            print(1);
            return;
        }
        else if(len1==lenS(0,0,x,y)&&len2==lenS(8,0,x,y)&&len3==lenS(1,5,x,y)){
            print(2);
            return;
        }
        else if(len1==lenC(0,0,x,y)&&len2==lenC(8,0,x,y)&&len3==lenC(1,5,x,y)){
            print(3);
            return;
        }
        else if(len1==lenM(0,0,x,y)&&len2==lenM(8,0,x,y)&&len3==lenM(1,5,x,y)){
            print(4);
            return;
        }
        else if(len1==lenX(0,0,x,y)&&len2==lenX(8,0,x,y)&&len3==lenX(1,5,x,y)){
            print(5);
            return;
        }
        else if(len1==lenB(0,0,x,y)&&len2==lenB(8,0,x,y)&&len3==lenB(1,5,x,y)){
            print(6);
            return;
        }
    }
    return;
}
signed main()
{
    solve();
    return 0;
}
/*
90
0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8
1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8
2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8
3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8
4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8
5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8
6 0 6 2 6 3 6 1 6 4 6 5 6 6 6 7 6 8
7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8
8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8
9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3940kb

input:

1
9 0
8

output:

1
? 1 8
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3836kb

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: 1ms
memory: 3884kb

input:

1
2 4
-1
1

output:

2
? 0 0
? 0 2
! X

result:

ok number is guessed.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

score: 0
Accepted
time: 1ms
memory: 4172kb

input:

1
6 0
6

output:

1
? 0 2
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 1ms
memory: 3940kb

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: 1ms
memory: 4200kb

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: 1ms
memory: 3968kb

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: 1ms
memory: 4016kb

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: -100
Wrong Answer
time: 1ms
memory: 3976kb

input:

8
3 3
2 5
6 2
7 4
1 4
3 0
2 4
3 4

output:

3
? 0 0

result:

wrong answer solution think m=3, while jury think m=2.