QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709937 | #9537. Chinese Chess | shmilyc | WA | 35ms | 3964kb | C++23 | 17.2kb | 2024-11-04 17:31:29 | 2024-11-04 17:31:29 |
Judging History
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;
}
}
}
// 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;
bool flag=true;
for(int len1=-1;len1<=20;len1++)
for(int len2=-1;len2<=20;len2++){
int cnt=0;
int check[7]={0};
for(int i=0;i<a.size();i++){
int x=a[i].r;
int y=a[i].c;
if(lenJ(r1,c1,x,y)==len1&&lenJ(r2,c2,x,y)==len2){
if(check[1]==0){
check[1]=1;
cnt++;
}
}
if(lenS(r1,c1,x,y)==len1&&lenS(r2,c2,x,y)==len2){
if(check[2]==0){
check[2]=1;
cnt++;
}
}
if(lenC(r1,c1,x,y)==len1&&lenC(r2,c2,x,y)==len2){
if(check[3]==0){
check[3]=1;
cnt++;
}
}
if(lenM(r1,c1,x,y)==len1&&lenM(r2,c2,x,y)==len2){
if(check[4]==0){
check[4]=1;
cnt++;
}
}
if(lenX(r1,c1,x,y)==len1&&lenX(r2,c2,x,y)==len2){
if(check[5]==0){
check[5]=1;
cnt++;
}
}
if(lenB(r1,c1,x,y)==len1&&lenB(r2,c2,x,y)==len2){
if(check[6]==0){
check[6]=1;
cnt++;
}
}
}
// if(r1==0&&r2==0&&c1==0&&c2==6&&len1==-1&&len2==-1){
// cout<<"????"<<cnt<<endl;
// for(int i=1;i<=6;i++)
// cout<<check[i]<<' ';cout<<endl;
// cout<<lenB(0,0,2,3)<<' '<<lenB(0,6,2,3)<<endl;
// cout<<lenS(0,0,2,3)<<' '<<lenS(0,6,2,3)<<endl;
// }
if(cnt>=2)
flag=false;
}
//两次查询 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||n==9){//这两个点满足两次问询得到答案
// return;
int len1,len2;
cout<<2<<endl;
cout.flush();
if(n==9){
r1=0;c1=0;
r2=3;c2=1;
}
ask(r1,c1,len1);
ask(r2,c2,len2);
// return;
for(int i=0;i<a.size();i++){
int x=a[i].r;
int y=a[i].c;
if(lenJ(r1,c1,x,y)==len1&&lenJ(r2,c2,x,y)==len2){
print(1);
return;
}
else if(lenS(r1,c1,x,y)==len1&&lenS(r2,c2,x,y)==len2){
print(2);
return;
}
else if(lenC(r1,c1,x,y)==len1&&lenC(r2,c2,x,y)==len2){
print(3);
return;
}
else if(lenM(r1,c1,x,y)==len1&&lenM(r2,c2,x,y)==len2){
print(4);
return;
}
else if(lenX(r1,c1,x,y)==len1&&lenX(r2,c2,x,y)==len2){
print(5);
return;
}
else if(lenB(r1,c1,x,y)==len1&&lenB(r2,c2,x,y)==len2){
print(6);
return;
}
}
// 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;
// }
// }
}
}
}
// 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: 3944kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 13ms
memory: 3852kb
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: 3940kb
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: 3820kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 10ms
memory: 3948kb
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: 25ms
memory: 3948kb
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: 30ms
memory: 3896kb
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: 35ms
memory: 3908kb
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: 35ms
memory: 3964kb
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: 0ms
memory: 3952kb
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8 -1 -1
output:
2 ? 0 0 ? 3 1 ! S
result:
wrong answer correct but in a random way.(2 8 6)