QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426504#8748. 简单博弈ucup-team1004WA 161ms12056kbC++144.2kb2024-05-31 13:18:062024-05-31 13:34:04

Judging History

This is the latest submission verdict.

  • [2024-05-31 13:34:04]
  • 管理员手动重测该提交记录
  • Verdict: WA
  • Time: 161ms
  • Memory: 12056kb
  • [2024-05-31 13:18:06]
  • 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,INF=1e9;
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=8;
int f[M][N][N];
void init(int n=N-1){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[0][i][j]=mex({
				f[0][i-1][j],f[0][i][j-1],f[0][i-1][j-1]
			});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[1][i][j]=mex({
				i>1?f[1][i-1][j]:INF,
				j>1?f[1][i][j-1]:INF,
				j>1?f[0][i-1][j]:INF,
				i>1?f[0][i][j-1]:INF,
				i>1&&j>1?f[1][i-1][j-1]:INF,
				i>1||j>1?f[0][i-1][j-1]:INF
			});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=2;j<=n;j++){
			f[2][i][j]=mex({
				i>1?f[2][i-1][j]:INF,
				j>2?f[2][i][j-1]:INF,
				j>2?f[0][i-1][j]:INF,
				i>1?f[1][i][j-1]:INF,
				i>1&&j>2?f[2][i-1][j-1]:INF,
				i>1?f[1][i-1][j-1]:INF,
				j>2?f[0][i-1][j-1]:INF
			});
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=2;j<=n;j++){
			f[3][i][j]=mex({
				i>2?f[3][i-1][j]:INF,
				j>2?f[3][i][j-1]:INF,
				f[1][i-1][j],f[1][i][j-1],
				i>2&&j>2?f[3][i-1][j-1]:INF,
				f[1][i-1][j-1],f[0][i-1][j-1]
			});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=3;j<=n;j++){
			f[4][i][j]=mex({
				i>1?f[4][i-1][j]:INF,
				j>3?f[4][i][j-1]:INF,
				j>3?f[0][i-1][j]:INF,
				i>1?f[2][i][j-1]:INF,
				i>1&&j>3?f[4][i-1][j-1]:INF,
				i>1?f[2][i-1][j-1]:INF,
				f[0][i-1][j-1]
			});
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=2;j<=n;j++){
			f[5][i][j]=mex({
				i>2?f[5][i-1][j]:INF,
				j>2?f[5][i][j-1]:INF,
				f[2][i-1][j],f[2][j-1][i],
				j>2?f[1][i-1][j]:INF,
				i>2?f[1][i][j-1]:INF,
				i>2&&j>2?f[5][i-1][j-1]:INF,
				j>2?f[2][i-1][j-1]:INF,
				i>2?f[2][j-1][i-1]:INF,
				f[1][i-1][j-1],f[0][i-1][j-1]
			});
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=3;j<=n;j++){
			f[6][i][j]=mex({
				i>2?f[6][i-1][j]:INF,
				j>3?f[6][i][j-1]:INF,
				f[2][i-1][j],f[1][i-1][j],
				f[2][i][j-1],f[3][i][j-1],
				i>2&&j>3?f[6][i-1][j-1]:INF,
				f[2][i-1][j-1],
				i>2?f[3][i-1][j-1]:INF,
				f[1][i-1][j-1],f[0][i-1][j-1]
			});
		}
	}
	for(int i=3;i<=n;i++){
		for(int j=3;j<=n;j++){
			f[7][i][j]=mex({
				i>3?f[7][i-1][j]:INF,
				j>3?f[7][i][j-1]:INF,
				f[3][i-1][j],
				f[3][i][j-1],
				i>3&&j>3?f[7][i-1][j-1]:INF,
				f[3][i-1][j-1],f[1][i-1][j-1],f[0][i-1][j-1]
			});
		}
	}
}
int res;
void get(){
	cin>>n>>m;
	for(int i=0;i<3;i++){
		cin>>x[i]>>y[i];
	}
	int tx=1,ty=1;
	for(int i=1;i<3;i++)tx+=x[i]!=x[i-1];
	for(int i=1;i<3;i++)ty+=y[i]!=y[i-1];
	if(tx==1&&ty==3)res^=f[4][n][m];
	else if(tx==3&&ty==1)res^=f[4][m][n];
	else if(tx==2&&ty==2)res^=f[5][n][m];
	else if(tx==3&&ty==3)res^=f[7][n][m];
	else if(tx==2&&ty==3)res^=f[6][n][m];
	else if(tx==3&&ty==2)res^=f[6][m][n];
	else assert(0);
}
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: 100
Accepted
time: 148ms
memory: 11796kb

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

result:

ok single line: 'OvO'

Test #2:

score: -100
Wrong Answer
time: 161ms
memory: 12056kb

input:

100000
494 303
141 173
343 269
451 163
4 370
4 46
1 100
3 135
226 3
21 3
116 1
47 3
77 52
65 27
19 4
69 50
205 235
164 101
106 183
27 16
4 2
3 2
1 2
4 2
364 364
54 50
155 83
21 181
432 434
295 302
332 91
258 264
324 326
136 171
239 155
300 81
1 4
1 3
1 2
1 4
177 435
20 326
170 256
175 179
1 4
1 3
1 ...

output:

OvO

result:

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