QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#699674 | #9537. Chinese Chess | ucup-team3586# | TL | 0ms | 0kb | C++23 | 3.0kb | 2024-11-02 10:21:53 | 2024-11-02 10:21:53 |
answer
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
// #define int long long
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int a[6][10][9][10][9];
vector<pair<int,int>> op[6];
#define xqw vector<pair<int,pair<int,int>>>
const string str="JSCMXB";
// map<xqw,bool> mp;
map<xqw,pair<int,int>> mp;
pair<int,int> F(xqw &f,int req)
{
int c=f[0].first;
bool ok=1;
for(auto i:f) ok&=(i.first==c);
if(ok) return {0,0};
if(req==0) return {-1,-1};
if(mp.count(f)) return mp[f];
for(int i=0; i<10; ++i)
for(int j=0; j<9; ++j)
{
xqw t[103];
for(auto [p,_]:f)
{
auto [q,r]=_;
t[a[p][q][r][i][j]+1].push_back({p,_});
}
bool gg=0;
for(int k=0; k<100; ++k)
if(t[k].size()==f.size()) gg=1;
if(gg) continue;
int cur=1;
for(int k=0; k<100; ++k)
if(!t[k].empty())
cur&=F(t[k],req-1).first!=-1;
// ans=min(ans,cur+1);
if(cur) return mp[f]={i,j};
}
return mp[f]={-1,-1};
// return mp[f]=ans;
}
int _o=5,_x,_y;
void dfs(xqw &f)
{
assert(!f.empty());
int c=f[0].first;
bool ok=1;
for(auto i:f) ok&=(i.first==c);
if(ok)
{
printf("! ");
putchar(str[c]);
fflush(stdout);
exit(0);
}
auto [i,j]=mp[f];
// assert(i!=-1);
printf("? %d %d\n",i,j);fflush(stdout);
int res=read();
// int res=a[_o][_x][_y][i][j];
xqw nxt;
for(auto [p,_]:f)
{
auto [q,r]=_;
if(a[p][q][r][i][j]==res)
nxt.push_back({p,_});
}
dfs(nxt);
return ;
}
signed main()
{
memset(a,-1,sizeof(a));
op[0]={{1,0},{-1,0},{0,1},{0,-1}};
op[1]={{1,1},{-1,-1},{1,-1},{-1,1}};
for(int i=1; i<=9; ++i)
op[2].push_back({i,0}),
op[2].push_back({-i,0}),
op[2].push_back({0,i}),
op[2].push_back({0,-i});
op[3]={{2,1},{2,-1},{-2,1},{-2,-1},{1,-2},{1,2},{-1,-2},{-1,2}};
op[4]={{2,2},{-2,-2},{-2,2},{2,-2}};
op[5]={{1,0},{0,-1},{0,1}};
for(int d=0; d<6; ++d)
for(int i=0; i<10; ++i)
for(int j=0; j<9; ++j)
{
a[d][i][j][i][j]=0;
queue<pair<int,int>> q;
q.push({i,j});
while(!q.empty())
{
auto [x,y]=q.front();q.pop();
if(d==5&&x<=4)
{
a[d][i][j][x+1][y]=a[d][i][j][x][y]+1;
q.push({x+1,y});
continue;
}
for(auto [dx,dy]:op[d])
{
if(a[d][i][j][x+dx][y+dy]==-1
&&0<=x+dx&&x+dx<10
&&0<=y+dy&&y+dy<9)
a[d][i][j][x+dx][y+dy]=a[d][i][j][x][y]+1,
q.push({x+dx,y+dy});
}
}
}
vector<pair<int,pair<int,int>>> vec;
int TTT=read();
int B=rand()%TTT;
for(int T=TTT; T--;)
{
int x=read(),y=read();
if(B==T) _x=x,_y=y;
for(int i=0; i<6; ++i)
vec.push_back({i,{x,y}});
}
// printf("%d %d %d\n",_o,_x,_y);
int T=1;
while(1)
{
mp.clear();
if(F(vec,T).first!=-1) break;
++T;
}
dfs(vec);
// printf("%d\n",T);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
1 9 0
output:
? 1 8