QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#702399#9537. Chinese Chessjapan406364961 (Ryo Takahashi, Masanori Ogiwara, Takuto Koriyama)#RE 0ms0kbC++205.4kb2024-11-02 15:54:472024-11-02 15:54:48

Judging History

This is the latest submission verdict.

  • [2024-11-02 15:54:48]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-11-02 15:54:47]
  • Submitted

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

result: