QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426486#8748. 简单博弈ucup-team1004WA 1479ms34556kbC++144.8kb2024-05-31 12:41:322024-05-31 12:41:32

Judging History

This is the latest submission verdict.

  • [2024-05-31 12:41:32]
  • Judged
  • Verdict: WA
  • Time: 1479ms
  • Memory: 34556kb
  • [2024-05-31 12:41:32]
  • 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=30;
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();
}
int res;
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;
	res^=dfs(find(a),n,m);
}
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();
	puts(res?"OvO":"QAQ");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1479ms
memory: 34556kb

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:

QAQ

result:

wrong answer 1st lines differ - expected: 'OvO', found: 'QAQ'