QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#711428 | #9537. Chinese Chess | shmilyc | WA | 1ms | 4156kb | C++23 | 15.5kb | 2024-11-05 10:45:50 | 2024-11-05 10:45:51 |
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 c1=0;c1<=8;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++){
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);
break;
}
}
if(findif){//对于这个距离没有合适的第二次查询
flag=false;
}
}
if(flag==true){//这两个点满足两次问询得到答案
// return;
int len1,len2;
cout<<2<<endl;
cout.flush();
ask(r1,c1,len1);
ask(ans[len1].first,ans[len2].second,len2);
int r2=ans[len1].first;int c2=ans[len1].second;
for(int i=0;i<a.size();i++){
int r=a[i].r;int c=a[i].c;
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==lenJ(r,c,r2,c2)){
print(3);
return;
}
if(len1==lenM(r,c,r1,c1)&&len2==lenJ(r,c,r2,c2)){
print(4);
return;
}
if(len1==lenX(r,c,r1,c1)&&len2==lenJ(r,c,r2,c2)){
print(5);
return;
}
if(len1==lenB(r1,c1,r,c)&&len2==lenJ(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
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4100kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 4156kb
input:
4 2 1 2 3 2 5 2 7 5 5
output:
2 ? 0 0 ? 0 0 ! J
result:
wrong answer correct but in a random way.(2 7 4)