QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426477#8748. 简单博弈ucup-team1004WA 1460ms24692kbC++144.8kb2024-05-31 12:32:532024-05-31 12:32:54

Judging History

This is the latest submission verdict.

  • [2024-05-31 12:32:54]
  • Judged
  • Verdict: WA
  • Time: 1460ms
  • Memory: 24692kb
  • [2024-05-31 12:32:53]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),x.end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<class S,class T>
ostream& operator << (ostream &out,pair<S,T> a);
template<class T>
ostream& operator << (ostream &out,vector<T> a);
template<class...T>
ostream& operator << (ostream &out,tuple<T...> a);
#ifdef DEBUG
template<class T>
void debug(T x);
template<class T,class...S>
void debug(T x,S...y);
#else
#define debug(...) void()
#endif
using ll=long long;
using ull=unsigned long long;
const int N=5e2+10;
int T,n,m,x[3],y[3];
int mex(vector<int>a){
	sort(all(a));
	a.erase(unique(all(a)),a.end());
	int res=0;
	for(;res<a.size()&&a[res]==res;res++);
	return res;
}
const int M=20;
int f[M][N][N];
using state=array<array<int,4>,4>;
state I;
ostream& operator << (ostream &out,array<int,4> a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
ostream& operator << (ostream &out,state a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
map<state,int>trs;
state cur[M];
int his[1<<9];
int find(state a){
	int S=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			S=S<<1|a[i][j];
		}
	}
	if(~his[S])return his[S];
	state las=a;
	array<int,4>p,q;
	iota(all(p),0);
	do{
		iota(all(q),0);
		do{
			state b;
			for(int i=0;i<4;i++){
				for(int j=0;j<4;j++){
					b[p[i]][q[j]]=las[i][j];
				}
			}
			a=min(a,b);
		}while(next_permutation(q.begin(),q.begin()+3));
	}while(next_permutation(p.begin(),p.begin()+3));
	if(trs.count(a))return his[S]=trs[a];
	int id=trs.size();
	// debug(id,a);
	return cur[id]=a,his[S]=trs[a]=id;
}
int dfs(int op,int n,int m){
	// debug(op,n,m);
	if(~f[op][n][m])return f[op][n][m];
	if(min(n,m)<1)return 0;
	state p=cur[op],q=p;
	for(int i=0;i<4;i++){
		for(int j=0;j<i;j++)swap(q[i][j],q[j][i]);
	}
	array<int,4>s,t;
	s.fill(0),t.fill(0);
	for(int i=0;i<min(n,4);i++){
		for(int j=0;j<min(m,4);j++){
			if(!p[i][j])s[i]=t[j]=1;
		}
	}
	vector<int>res;
	for(int i=0;i<min(n,4);i++)if(s[i]){
		if(i&&p[i]==p[i-1])continue;
		state ne=I;
		for(int x=0;x<min(n,4);x++)if(x^i){
			for(int y=0;y<min(m,4);y++){
				ne[x-(x>i)][y]=p[x][y];
			}
		}
		res.push_back(dfs(find(ne),n-1,m));
	}
	for(int j=0;j<min(m,4);j++)if(t[j]){
		if(j&&q[j]==q[j-1])continue;
		state ne=I;
		for(int x=0;x<min(n,4);x++){
			for(int y=0;y<min(m,4);y++)if(y^j){
				ne[x][y-(y>j)]=p[x][y];
			}
		}
		res.push_back(dfs(find(ne),n,m-1));
	}
	for(int i=0;i<min(n,4);i++){
		if(i&&p[i]==p[i-1])continue;
		for(int j=0;j<min(m,4);j++){
			if(j&&q[j]==q[j-1])continue;
			if(!s[i]&&!t[j])continue;
			state ne=I;
			for(int x=0;x<min(n,4);x++)if(x^i){
				for(int y=0;y<min(m,4);y++)if(y^j){
					ne[x-(x>i)][y-(y>j)]=p[x][y];
				}
			}
			res.push_back(dfs(find(ne),n-1,m-1));
		}
	}
	return f[op][n][m]=mex(res);
}
void init(int n=N-1){
	memset(his,-1,sizeof his);
	memset(f,-1,sizeof f);
	// state a;
	// a=I;
	// a[0][0]=a[1][1]=a[2][2]=1;
	// int u=find(a);
	// for(int i=1;i<=n;i++){
	// 	for(int j=1;j<=n;j++){
	// 		dfs(u,i,j);
	// 	}
	// }
	// // debug("OK");
	// a[2][2]=0,a[1][2]=1;
	// u=find(a);
	// for(int i=1;i<=n;i++){
	// 	for(int j=1;j<=n;j++){
	// 		dfs(u,i,j);
	// 	}
	// }
	// a=I;
	// a[0][0]=a[0][1]=a[1][0]=1;
	// u=find(a);
	// for(int i=1;i<=n;i++){
	// 	for(int j=1;j<=n;j++){
	// 		dfs(u,i,j);
	// 	}
	// }
	// a=I;
	// a[0][0]=a[0][1]=a[0][2]=1;
	// u=find(a);
	// for(int i=1;i<=n;i++){
	// 	for(int j=1;j<=n;j++){
	// 		dfs(u,i,j);
	// 	}
	// }
}
void reduce(int *x){
	vector<int>nx{x,x+3};
	sort(all(nx)),nx.erase(unique(all(nx)),nx.end());
	for(int i=0;i<3;i++)x[i]=lower_bound(all(nx),x[i])-nx.begin();
}
void get(){
	cin>>n>>m;
	for(int i=0;i<3;i++){
		cin>>x[i]>>y[i];
	}
	reduce(x),reduce(y);
	state a=I;
	for(int i=0;i<3;i++)a[x[i]][y[i]]=1;
	puts(dfs(find(a),n,m)?"OvO":"QAQ");
}
void clr(){}
template<bool x>
using If=typename enable_if<x>::type;
template<int i,class T>
If<i==0> otp(ostream &out,T a){
	out<<get<i>(a);
}
template<int i,class T>
If<i!=0> otp(ostream &out,T a){
	otp<i-1>(out,a),out<<','<<get<i>(a);
}
template<class...T>
ostream& operator << (ostream &out,tuple<T...> a){
	return out<<'(',otp<sizeof...(T)-1>(out,a),out<<')';
}
template<class S,class T>
ostream& operator << (ostream &out,pair<S,T> a){
	return out<<'('<<a.first<<','<<a.second<<')';
}
template<class T>
ostream& operator << (ostream &out,vector<T> a){
	out<<'[';
	for(auto x:a)out<<x<<',';
	return out<<']';
}
#ifdef DEBUG
template<class T>
void debug(T x){
	cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
#endif
int main(){
	int T;
	scanf("%d",&T);
	for(init();T--;clr())get();
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1460ms
memory: 24692kb

input:

100000
215 4
6 1
59 1
71 4
1 482
1 311
1 381
1 26
3 428
3 81
2 359
1 310
222 220
108 40
16 2
11 79
4 223
4 73
4 103
3 51
214 442
174 261
186 418
202 379
146 464
61 193
85 102
117 206
3 1
3 1
2 1
1 1
357 356
199 222
97 15
257 15
30 2
28 2
4 1
12 2
308 308
32 110
56 157
234 171
347 346
243 89
166 140
...

output:

OvO
OvO
OvO
QAQ
OvO
QAQ
QAQ
OvO
OvO
QAQ
QAQ
OvO
OvO
QAQ
OvO
OvO
OvO
QAQ
OvO
OvO
OvO
OvO
OvO
OvO
QAQ
OvO
OvO
OvO
QAQ
OvO
OvO
QAQ
QAQ
OvO
OvO
OvO
OvO
OvO
QAQ
OvO
OvO
QAQ
QAQ
OvO
QAQ
OvO
OvO
OvO
OvO
OvO
QAQ
OvO
OvO
OvO
OvO
QAQ
QAQ
QAQ
OvO
OvO
QAQ
OvO
QAQ
OvO
OvO
QAQ
OvO
OvO
OvO
OvO
OvO
OvO
QAQ
OvO
OvO
...

result:

wrong output format Extra information in the output file