QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709763#9537. Chinese ChessshmilycWA 40ms4156kbC++2312.6kb2024-11-04 16:41:132024-11-04 16:41:16

Judging History

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

  • [2024-11-04 16:41:16]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:4156kb
  • [2024-11-04 16:41:13]
  • 提交

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));
        }
    }
    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()
{
    // 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;
            }
        }
    }
    if(n<50){
        //两次查询能查结束,说明对每一种棋子,在所有输入点中,只存在一种可能情况
        for(int r1=0;r1<=9;r1++)
            for(int r2=0;r2<=9;r2++)
                for(int c1=0;c1<=8;c1++)
                    for(int c2=0;c2<=8;c2++){
                    if(r1==r2&&c1==c2)
                        continue;
                    //两次查询  r1,r2,c1,c2
                    map<int,vector<Point>> m1,m2;
                    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));

                        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));
                    }
                    bool flag=true;
                    for(auto temp1:m1){  //第一次查询
                        for(auto temp2:m2){//第二次查询
                            //对于所有第一次查询出的距离和第二次查询出的距离
                            int check[7]={0};//判断这种返回情况是否属实
                            int cnt=0;
                            //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
                                        // &&(temp1.first!=-1||temp2.first!=-1)
                                    ){//属于同一种情况
                                        if(check[temp1.second[q].pos]==0){
                                            check[temp1.second[q].pos]=1;
                                            cnt++;
                                            if(cnt==2){
                                                flag=false;
                                                break;
                                            }
                                        }
                                    }
                                }
                            if(flag==false)
                                break;
                            // if(cnt>1){
                            //     cout<<r1<<' '<<c1<<'-'<<r2<<' '<<c2<<endl;
                            //     cout<<"?"<<temp1.first<<" "<<temp2.first<<" "<<cnt<<endl;
                            // }
                        }
                        if(flag==false)
                            break;
                    }

                    if(flag==true){//这两个点满足两次问询得到答案
                        int len1,len2;
                        cout<<2<<endl;
                        cout.flush();
                        ask(r1,c1,len1);
                        ask(r2,c2,len2);
                        for(int i=0;i<m1[len1].size();i++)
                            for(int j=0;j<m2[len2].size();j++){
                                if(m1[len1][i].c==m2[len2][j].c
                                    &&m1[len1][i].r==m2[len2][j].r
                                    &&m1[len1][i].pos==m2[len2][j].pos
                                ){
                                    print(m1[len1][i].pos);
                                    return;
                                }
                            }
                    }
                }
    }
    // 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: 3916kb

input:

1
9 0
8

output:

1
? 1 8
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 2ms
memory: 4156kb

input:

4
2 1
2 3
2 5
2 7
5
2

output:

2
? 0 0
? 5 4
! M

result:

ok number is guessed.

Test #3:

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

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: 3928kb

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

1
6 0
6

output:

1
? 0 2
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3944kb

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: 2ms
memory: 3932kb

input:

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

output:

2
? 0 0
? 8 1
! M

result:

ok number is guessed.

Test #8:

score: 0
Accepted
time: 0ms
memory: 3948kb

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: 3ms
memory: 4004kb

input:

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

output:

2
? 0 0
? 8 7
! M

result:

ok number is guessed.

Test #10:

score: 0
Accepted
time: 3ms
memory: 4052kb

input:

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

output:

2
? 0 1
? 7 7
! S

result:

ok number is guessed.

Test #11:

score: -100
Wrong Answer
time: 40ms
memory: 3884kb

input:

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

output:

3
? 0 0

result:

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