QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #706333 | #9537. Chinese Chess | Brno (Bocheng Jiang, Zhenyu Wang, Taixiang Wang) | TL | 406ms | 29276kb | C++14 | 4.8kb | 2024-11-03 10:37:07 | 2024-11-03 10:37:08 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
#define MID int mid=(l+r)>>1;
#define ll long long
// #define endl '\n'
#define siz(a) int(a.size())
struct node{
int x,y,tp;
}p[400100];
vector<node>a,to[400100];
bool operator<(const node&a,const node&b){
return a.tp==b.tp?a.x==b.x?a.y<b.y:a.x<b.x:a.tp<b.tp;
}
map<vector<node>,int>id;
map<pair<int,vector<node>>,int>mp;
vector<pair<int,int>>g[200100];
int n,dis[20][20][10][20][20],tot;
int x1[]={1,-1,0,0},y11[]={0,0,-1,1};
int x2[]={1,1,-1,-1},y2[]={1,-1,1,-1};
int x4[]={2,2,-2,-2,1,1,-1,-1},y4[]={1,-1,1,-1,2,-2,2,-2};
int x5[]={2,2,-2,-2},y5[]={2,-2,2,-2};
int x6[]={1,0,0},y6[]={0,1,-1};
char wcnm[]={' ','J','S','C','M','X','B'};
void solveclr(){
}
bool cmp(node a,node b){
return a.tp<b.tp;
}
int getid(vector<node> a){
if(!id.count(a)){
to[++tot]=a;
return id[a]=tot;
}
else return id[a];
}
int dfs(int d,vector<node>&a){
if(d>4)return 0x3f3f3f3f;
if(mp.count(mk(d,a)))return mp[mk(d,a)];
if(a[0].tp==a[a.size()-1].tp){return 0;}
vector<node>val[100];
int ans=0x3f3f3f3f;
for(int i=0;i<=9;i++){
for(int j=0;j<=8;j++){
for(int i=0;i<=90;i++)val[i].clear();
for(node tmp:a){
// cout<<dis[tmp.x][tmp.y][tmp.tp][i][j]<<' ';
val[dis[tmp.x][tmp.y][tmp.tp][i][j]].push_back(tmp);
}
// cout<<endl;
int now=0,fl=0;
for(int i=0;i<=90;i++){
if(val[i].size()==a.size()){fl=1;break;}
}
if(fl)continue;
for(int i=0;i<=90;i++){
if(val[i].size())now=max(now,dfs(d+1,val[i]));
}
// if(d==0)cout<<ans<<' '<<now+1<<endl;
if(ans>now+1){
// cout<<d<<':';
ans=now+1;
int u=getid(a);
g[u].clear();
p[u].x=i,p[u].y=j;
for(int i=0;i<=90;i++){
if(val[i].size())g[u].push_back(mk(getid(val[i]),i-1));
}
}
}
}
mp[mk(d,a)]=ans;
// if(d==1){cout<<d<<':';
// for(auto tmp:a)cout<<tmp.tp<<' ';
// cout<<endl<<ans<<endl;}
return ans;
}
bool ck(int x,int y){
return x>=0&&y>=0&&x<=9&&y<=8;
}
void calc(){
queue<node>q;
memset(dis,0,sizeof(dis));
for(int r=0;r<=9;r++){
for(int c=0;c<=9;c++){
for(int tp=1;tp<=6;tp++){
dis[r][c][tp][r][c]=1;
q.push(node{r,c,tp});
while(!q.empty()){
node u=q.front();q.pop();
if(tp==1){
for(int i=0;i<4;i++){
node v=u;v.x+=x1[i],v.y+=y11[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==2){
for(int i=0;i<4;i++){
node v=u;v.x+=x2[i],v.y+=y2[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==3){
for(int i=-9;i<=9;i++){
node v=u;v.x+=i;
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
for(int i=-9;i<=9;i++){
node v=u;v.y+=i;
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==4){
for(int i=0;i<8;i++){
node v=u;v.x+=x4[i],v.y+=y4[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==5){
for(int i=0;i<4;i++){
node v=u;v.x+=x5[i],v.y+=y5[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==6){
if(u.x>4)for(int i=0;i<3;i++){
node v=u;v.x+=x6[i],v.y+=y6[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
else{
node v=u;v.x++;
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
}
}
}
}
}
void solve(){
solveclr();
calc();
cin>>n;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
for(int i=1;i<=6;i++)a.push_back(node{x,y,i});
}
sort(a.begin(),a.end(),cmp);
int m=dfs(0,a);
cout<<m<<endl;
int now=id[a],in;
for(int i=1;i<=m;i++){
if(to[now].size()==1){
cout<<"? "<<1<<' '<<1<<endl;cin>>in;continue;
}
cout<<"? "<<p[now].x<<' '<<p[now].y<<endl;
cin>>in;
for(auto tmp:g[now]){
if(tmp.second==in){
now=tmp.first;
break;
}
}
}
cout<<"! "<<wcnm[to[now][0].tp]<<endl;
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT;
// cin>>TTT;
TTT=1;
while(TTT--)solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 25276kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 35ms
memory: 25900kb
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: 3ms
memory: 24368kb
input:
1 2 4 -1 1
output:
2 ? 0 0 ? 0 2 ! X
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 4ms
memory: 25040kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 4ms
memory: 25936kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 10ms
memory: 24572kb
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: 84ms
memory: 24728kb
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: 124ms
memory: 25888kb
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: 249ms
memory: 26220kb
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: 0
Accepted
time: 305ms
memory: 27092kb
input:
8 3 3 2 5 6 2 7 4 1 4 3 0 2 4 3 4 7 -1
output:
2 ? 0 1 ? 0 0 ! S
result:
ok number is guessed.
Test #11:
score: 0
Accepted
time: 406ms
memory: 29012kb
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8 6 8
output:
2 ? 2 0 ? 0 0 ! J
result:
ok number is guessed.
Test #12:
score: 0
Accepted
time: 193ms
memory: 26120kb
input:
10 4 0 0 0 5 0 7 0 8 0 1 0 6 0 9 0 2 0 3 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #13:
score: 0
Accepted
time: 361ms
memory: 29156kb
input:
9 1 8 1 2 1 5 1 6 1 3 1 4 1 0 1 1 1 7 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #14:
score: 0
Accepted
time: 151ms
memory: 27256kb
input:
10 0 4 5 4 8 4 2 4 4 4 7 4 3 4 9 4 6 4 1 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #15:
score: 0
Accepted
time: 213ms
memory: 27156kb
input:
9 4 6 4 5 4 7 4 4 4 1 4 3 4 0 4 8 4 2 6 12
output:
2 ? 4 2 ? 0 0 ! J
result:
ok number is guessed.
Test #16:
score: 0
Accepted
time: 185ms
memory: 26148kb
input:
10 9 2 5 2 1 2 8 2 6 2 7 2 2 2 0 2 4 2 3 2 10 3
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #17:
score: 0
Accepted
time: 322ms
memory: 27648kb
input:
9 3 1 3 7 3 5 3 3 3 6 3 4 3 0 3 2 3 8 6 11
output:
2 ? 3 2 ? 0 0 ! J
result:
ok number is guessed.
Test #18:
score: 0
Accepted
time: 183ms
memory: 26184kb
input:
10 5 1 8 1 6 1 4 1 3 1 0 1 2 1 7 1 9 1 1 1 10 -1
output:
2 ? 9 0 ? 0 0 ! B
result:
ok number is guessed.
Test #19:
score: 0
Accepted
time: 370ms
memory: 29276kb
input:
9 1 6 1 4 1 3 1 7 1 8 1 5 1 2 1 1 1 0 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #20:
score: 0
Accepted
time: 190ms
memory: 26996kb
input:
10 5 0 9 0 1 0 2 0 3 0 6 0 7 0 4 0 0 0 8 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #21:
score: 0
Accepted
time: 329ms
memory: 28380kb
input:
9 0 3 0 5 0 7 0 0 0 4 0 8 0 1 0 6 0 2 6 5
output:
2 ? 0 0 ? 0 1 ! J
result:
ok number is guessed.
Test #22:
score: 0
Accepted
time: 188ms
memory: 26612kb
input:
10 1 0 9 0 4 0 2 0 8 0 7 0 5 0 3 0 0 0 6 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #23:
score: 0
Accepted
time: 372ms
memory: 28408kb
input:
9 1 8 1 2 1 7 1 0 1 4 1 6 1 1 1 5 1 3 6 7
output:
2 ? 1 0 ? 0 0 ! J
result:
ok number is guessed.
Test #24:
score: 0
Accepted
time: 155ms
memory: 25568kb
input:
10 2 4 1 4 0 4 6 4 4 4 9 4 5 4 3 4 7 4 8 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #25:
score: 0
Accepted
time: 334ms
memory: 28168kb
input:
9 0 2 0 7 0 5 0 4 0 0 0 3 0 1 0 6 0 8 6 5
output:
2 ? 0 0 ? 0 1 ! J
result:
ok number is guessed.
Test #26:
score: 0
Accepted
time: 173ms
memory: 27380kb
input:
10 5 3 2 3 3 3 8 3 9 3 1 3 6 3 7 3 0 3 4 3 11 4
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #27:
score: -100
Time Limit Exceeded
input:
50 7 5 9 2 0 4 9 3 8 4 8 2 7 2 6 4 4 4 0 0 1 7 1 1 1 5 2 0 9 8 9 0 3 1 7 8 8 6 5 0 7 3 8 5 2 6 4 8 3 5 6 8 0 8 5 7 4 6 1 6 3 8 5 6 3 0 5 3 0 7 5 1 3 4 0 1 7 6 2 3 4 3 5 5 8 1 0 3 6 5 9 5 5 8 7 4 6 3 2 7