QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#702399 | #9537. Chinese Chess | japan406364961 (Ryo Takahashi, Masanori Ogiwara, Takuto Koriyama)# | RE | 0ms | 0kb | C++20 | 5.4kb | 2024-11-02 15:54:47 | 2024-11-02 15:54:48 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<random>
#include<queue>
#include<vector>
#include<array>
#include<map>
#include<bitset>
#include<cassert>
using namespace std;
const bool debug=false;
const int H=10,W=9;
//using CAN=bitset<H*W*6>;
struct CAN{
static const int n=(H*W*6+64-1)/64;
array<long long,n>dat;
void reset(){dat.fill(0LL);}
bool test(int idx)const{return dat[idx/64]>>idx%64&1;}
void set(int idx){dat[idx/64]|=1LL<<idx%64;}
int count()const
{
int cnt=0;
for(int i=0;i<n;i++)cnt+=__builtin_popcountll(dat[i]);
return cnt;
}
bool operator<(const CAN&rhs)const
{
return dat<rhs.dat;
}
};
int dist[H*W*6][H*W];
tuple<int,int,int>rck(int v){return make_tuple(v/W/6,v/6%W,v%6);}
map<CAN,pair<int,int> >mp;
int dfs(CAN A,int limit)
{
if(mp.find(A)!=mp.end())return mp[A].first;
{//check end
int exk=0;
for(int i=0;i<H*W*6;i++)if(A.test(i))exk|=1<<i%6;
int pc=__builtin_popcount(exk);
assert(pc>=1);
if(pc==1)
{
mp[A]=make_pair(0,-1);
return 0;
}
}
if(limit==0)return 0;
assert(limit>=1);
vector<pair<int,int> >T[H*W];
for(int i=0;i<H*W*6;i++)if(A.test(i))
{
for(int v=0;v<H*W;v++)T[v].push_back(make_pair(dist[i][v],i));
}
vector<pair<int,CAN> >NXT[H*W];
vector<pair<int,int> >X;
for(int v=0;v<H*W;v++)
{
sort(T[v].begin(),T[v].end());
int mx=0;
for(int i=0;i<T[v].size();)
{
const int d=T[v][i].first;
CAN t;
t.reset();
int cnt=0;
while(i<T[v].size()&&T[v][i].first==d)
{
cnt++;
t.set(T[v][i++].second);
}
mx=max(mx,cnt);
NXT[v].push_back(make_pair(d,t));
}
if(NXT[v].size()>=2)X.push_back(make_pair(mx,v));
}
sort(X.begin(),X.end());
int tv=-1;
for(auto[_,v]:X)
{
int mx=0;
for(auto[_,B]:NXT[v])
{
int t=dfs(B,limit-1)+1;
mx=max(mx,t);
if(mx>=limit)break;
}
if(limit>mx)
{
limit=mx;
tv=v;
}
}
mp[A]=make_pair(limit,tv);
return limit;
}
int ANSWER;
int ask(int v)
{
assert(0<=v&&v<H*W);
cout<<"? "<<v/W<<" "<<v%W<<endl;
if(debug)return dist[ANSWER][v];
else
{
int r;cin>>r;
return r;
}
}
void solve(vector<int>Ain)
{
mp.clear();
CAN A;A.reset();
for(int a:Ain)for(int k=0;k<6;k++)A.set(a*6+k);
if(debug)cout<<"START dfs"<<endl;
int t=dfs(A,(int)1e9);
if(debug)cout<<"END dfs"<<endl;
assert(t<(int)1e9);
while(true)
{
assert(t>=0);
int exk=0;
for(int i=0;i<H*W*6;i++)if(A.test(i))exk|=1<<i%6;
int pc=__builtin_popcount(exk);
assert(pc>=1);
if(pc==1)
{
int k=0;
while(!(exk>>k&1))k++;
cout<<"! "<<"JSCMXB"[k]<<endl;
if(debug)assert(ANSWER%6==k);
return;
}
assert(t>=1);
assert(mp.find(A)!=mp.end());
assert(t>=mp[A].first);
t=mp[A].first;
int v=mp[A].second;
int ret=ask(v);
CAN B;B.reset();
for(int i=0;i<H*W*6;i++)if(A.test(i)&&dist[i][v]==ret)B.set(i);
A=B;
t--;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
for(int i=0;i<H*W*6;i++)
{
auto[r,c,k]=rck(i);
int TO[H*W];
for(int j=0;j<H*W;j++)TO[j]=1e9;
TO[r*W+c]=0;
if(k==2)
{//rook
for(int tr=0;tr<H;tr++)for(int tc=0;tc<W;tc++)
{
int v=tr*W+tc;
TO[v]=2;
if(tr==r)TO[v]--;
if(tc==c)TO[v]--;
}
}
else
{
queue<int>Q;Q.push(r*W+c);
while(!Q.empty())
{
int t=Q.front();Q.pop();
int r=t/W,c=t%W;
if(k==0)
{//king
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
for(int j=0;j<4;j++)
{
int tr=r+dx[j],tc=c+dy[j];
if(tr>=0&&tc>=0&&tr<H&&tc<W&&TO[tr*W+tc]>TO[t]+1)
{
TO[tr*W+tc]=TO[t]+1;
Q.push(tr*W+tc);
}
}
}
else if(k==1)
{//mandarin
const int dx[4]={1,1,-1,-1};
const int dy[4]={1,-1,1,-1};
for(int j=0;j<4;j++)
{
int tr=r+dx[j],tc=c+dy[j];
if(tr>=0&&tc>=0&&tr<H&&tc<W&&TO[tr*W+tc]>TO[t]+1)
{
TO[tr*W+tc]=TO[t]+1;
Q.push(tr*W+tc);
}
}
}
else if(k==3)
{//knight
const int dx[8]={2,2,-2,-2,1,1,-1,-1};
const int dy[8]={1,-1,1,-1,2,-2,2,-2};
for(int j=0;j<8;j++)
{
int tr=r+dx[j],tc=c+dy[j];
if(tr>=0&&tc>=0&&tr<H&&tc<W&&TO[tr*W+tc]>TO[t]+1)
{
TO[tr*W+tc]=TO[t]+1;
Q.push(tr*W+tc);
}
}
}
else if(k==4)
{//bishop
const int dx[4]={2,2,-2,-2};
const int dy[4]={2,-2,2,-2};
for(int j=0;j<4;j++)
{
int tr=r+dx[j],tc=c+dy[j];
if(tr>=0&&tc>=0&&tr<H&&tc<W&&TO[tr*W+tc]>TO[t]+1)
{
TO[tr*W+tc]=TO[t]+1;
Q.push(tr*W+tc);
}
}
}
else if(k==5)
{//pawn
{
int tr=r+1,tc=c;
if(tr>=0&&tc>=0&&tr<H&&tc<W&&TO[tr*W+tc]>TO[t]+1)
{
TO[tr*W+tc]=TO[t]+1;
Q.push(tr*W+tc);
}
}
if(r>4)
{
for(int tc:{c+1,c-1})
{
int tr=r;
if(tr>=0&&tc>=0&&tr<H&&tc<W&&TO[tr*W+tc]>TO[t]+1)
{
TO[tr*W+tc]=TO[t]+1;
Q.push(tr*W+tc);
}
}
}
}
else assert(false);
}
}
for(int j=0;j<H*W;j++)dist[i][j]=TO[j]==(int)1e9?-1:TO[j];
}
if(debug)
{
mt19937 rng(114514);
{
vector<int>A;
for(int i=0;i<90;i++)if(rng()%1==0)A.push_back(i);
assert(!A.empty());
ANSWER=A[rng()%A.size()]*6+rng()%6;
solve(A);
}
return 0;
}
int N;cin>>N;
vector<int>A(N);
for(int i=0;i<N;i++)
{
int r,c;cin>>r>>c;
A[i]=r*W+c;
}
solve(A);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
1 9 0
output:
? 1 8