QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710649#9537. Chinese ChessWrongAnswer_90WA 2ms5984kbC++237.6kb2024-11-04 20:50:582024-11-04 20:50:58

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 20:50:58]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5984kb
  • [2024-11-04 20:50:58]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair

//#define FastI
//#define FastO
#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[200000030],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
	int x,y,z;
	tup(int X=0,int Y=0,int Z=0)
	{x=X,y=Y,z=Z;}
	inline bool operator <(const tup t)const
	{return x<t.x||(x==t.x&&y<t.y)
	||(x==t.x&&y==t.y&&z<t.z);}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,200000030,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[40];
			int top=0;
			do st[top++]=x%10+'0',x/=10;while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' '&&st!='\r'&&st!='\0')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		char ch=getchar();s=0;
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-'&&(ch=getchar()));
		while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=tf?-s:s;
	}
	inline void edl(){putchar('\n');}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
	#ifdef FastO
	struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
	#endif
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
	inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	int n;
	vt ve;
	int t[10][10][10][10];
	inline int dis(int id,int x1,int y1,int x2,int y2)
	{
		if(id==1)return abs(x1-x2)+abs(y1-y2);
		else if(id==2)
		{
			if(((x1+x2)^(y1+y2))&1)return -1;
			return max(abs(x1-x2),abs(y1-y2));
		}
		else if(id==3)
		{
			if(x1==y1&&x2==y2)return 0;
			if(x1==y1||x2==y2)return 1;
			return 2;
		}
		else if(id==4)return t[x1][y1][x2][y2];
		else if(id==5)
		{
			if(((x1+x2)|(y1+y2))&1)return -1;
			if(((abs(x1-x2))^(abs(y1-y2)))&2)return -1;
			return max(abs(x1-x2),abs(y1-y2))>>1;
		}
		else
		{
			if(x2<=4&&y1!=y2)return -1;
			if(x2<x1)return -1;
			return abs(x1-x2)+abs(y1-y2);
		}
	}
	inline vt get(vt ve,int x,int y,int z)
	{
		vt tmp;
		for(auto [_x,_y,id]:ve)
		if(dis(id,_x,_y,x,y)==z)
		tmp.eb(tup(_x,_y,id));
		return tmp;
	}
	
	const int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={-2,-1,1,2,2,1,-1,-2};
	void init()
	{
		memset(t,127,sizeof(t));
		for(int i=0;i<=9;++i)for(int j=0;j<=8;++j)
		{
			queue<pii> q;
			t[i][j][i][j]=0;
			q.e(mp(i,j));
			while(!q.empty())
			{
				pii nw=q.front();q.pop();
				for(int k=0;k<8;++k)
				{
					int x=nw.fi+dx[k],y=nw.se+dy[k];
					if(x>=0&&y>=0&&x<=9&&y<=8&&t[i][j][x][y]>inf)
					{
						t[i][j][x][y]=t[i][j][nw.fi][nw.se]+1;
						q.e(mp(x,y));
					}
				}
			}
		}
	}
	map<vt,pii> ans;
	int p[20];
	bool dfs(vt ve,int dep)
	{
//		cerr<<dep<<endl;
		if(ans.find(ve)!=ans.end())return ans[ve].fi==-1?0:1;
		if(dep==0)
		{
			map<int,int> vis;
			for(auto [x,y,z]:ve)vis[z]=1;
			return vis.size()==1;
		}
		vector<tup> trans;
		vector<tup> tat[20];
		for(int x=0;x<=9;++x)for(int y=0;y<=8;++y)
		{
			for(int i=0;i<20;++i)tat[i].clear();
			int v=0;
			for(auto [_x,_y,id]:ve)
			tat[dis(id,_x,_y,x,y)+1].eb(tup(_x,_y,id));
			for(int i=0;i<20;++i)Mmax(v,(int)tat[i].size());
			if(v==(int)ve.size())continue;
			trans.eb(tup(v,x,y));
		}
		sort(all(trans),[&](tup x,tup y){return x.x<y.x;});
		for(auto [_v,x,y]:trans)
		{
			for(int i=0;i<20;++i)tat[i].clear();
			for(auto [_x,_y,id]:ve)
			tat[dis(id,_x,_y,x,y)+1].eb(tup(_x,_y,id));
			for(int i=0;i<20;++i)p[i]=i;
			sort(p,p+20,[&](int x,int y){return tat[x].size()>tat[y].size();});
			int fl=1;
			for(int i=0;i<20;++i)
			{
				if(tat[p[i]].empty())break;
				fl&=dfs(tat[p[i]],dep-1);
				if(!fl)break;
			}
			if(fl)
			{
				ans[ve]=mp(x,y);
				return 1;
			}
		}
		ans[ve]=mp(-1,-1);
		return 0;
	}
	char s[10]=" JSCMXB";
	void mian()
	{
		init();
		cin>>n;
		int x,y;
		vt ve;
		while(n--)
		{
			cin>>x>>y;
			for(int i=1;i<=6;++i)ve.eb(tup(x,y,i));
		}
		sort(ve.begin(),ve.end());
		for(int dep=1;;++dep)
		{
			ans.clear();
			if(dfs(ve,dep))
			{
				write(dep,'\n');
				while(dep--)
				{
					pii nw=ans[ve];
					cout<<"? "<<nw.fi<<" "<<nw.se<<endl;
					fflush(stdout);
					cin>>x;
					ve=get(ve,nw.fi,nw.se,x);
				}
//				cerr<<ve.size()<<endl;
				assert(ve.size());
				cout<<"! "<<s[ve.front().z]<<endl;
				fflush(stdout);
				break;
			}
		}
	}
	inline void Mian()
	{
		int T=1;
//		read(T);
		while(T--)mian();
	}
}
bool ED;
signed main()
{
//	ios::sync_with_stdio(0);
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	double st=clock();
	WrongAnswer_90::Mian();
	double ed=clock();
 	cerr<<endl;
 	cerr<<"Time: "<<ed-st<<" ms\n";
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5984kb

input:

1
9 0
6

output:

1
? 3 2
! S

result:

ok number is guessed.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

4
2 1
2 3
2 5
2 7
10
3

output:

2
? 8 5
? 0 0
! J

result:

ok number is guessed.

Test #3:

score: 0
Accepted
time: 1ms
memory: 4000kb

input:

1
2 4
-1
5

output:

2
? 6 1
? 7 5
! S

result:

ok number is guessed.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

1
5 0
6

output:

1
? 3 6
! S

result:

ok number is guessed.

Test #5:

score: 0
Accepted
time: 1ms
memory: 3996kb

input:

1
6 0
6

output:

1
? 0 2
! S

result:

ok number is guessed.

Test #6:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

2
7 7
1 0
5
14

output:

2
? 9 4
? 0 0
! J

result:

ok number is guessed.

Test #7:

score: 0
Accepted
time: 1ms
memory: 4180kb

input:

5
8 6
1 3
0 5
2 4
0 2
11
-1

output:

2
? 7 1
? 0 0
! B

result:

ok number is guessed.

Test #8:

score: 0
Accepted
time: 1ms
memory: 4184kb

input:

6
0 7
1 6
2 8
0 5
7 6
8 2
12
5

output:

2
? 9 8
? 0 0
! J

result:

ok number is guessed.

Test #9:

score: 0
Accepted
time: 1ms
memory: 3888kb

input:

7
6 5
3 0
3 2
4 1
4 0
2 4
5 2
13
4

output:

2
? 9 8
? 0 0
! J

result:

ok number is guessed.

Test #10:

score: 0
Accepted
time: 1ms
memory: 4040kb

input:

8
3 3
2 5
6 2
7 4
1 4
3 0
2 4
3 4
10
5

output:

2
? 9 6
? 0 0
! J

result:

ok number is guessed.

Test #11:

score: 0
Accepted
time: 0ms
memory: 4036kb

input:

9
2 7
2 4
2 5
2 2
2 1
2 0
2 6
2 3
2 8
11
9

output:

2
? 8 2
? 0 0
! J

result:

ok number is guessed.

Test #12:

score: 0
Accepted
time: 1ms
memory: 4176kb

input:

10
4 0
0 0
5 0
7 0
8 0
1 0
6 0
9 0
2 0
3 0
14
1

output:

2
? 9 6
? 0 0
! J

result:

ok number is guessed.

Test #13:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

9
1 8
1 2
1 5
1 6
1 3
1 4
1 0
1 1
1 7
11
-1

output:

2
? 6 6
? 0 0
! B

result:

ok number is guessed.

Test #14:

score: -100
Wrong Answer
time: 1ms
memory: 4012kb

input:

10
0 4
5 4
8 4
2 4
4 4
7 4
3 4
9 4
6 4
1 4
4
-1

output:

2
? 9 8
? 0 0
! X

result:

wrong answer correct but in a random way.(9 4 6)