QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424580#8748. 简单博弈ShaojiaZhangRE 0ms0kbC++173.8kb2024-05-29 13:33:392024-05-29 13:33:40

Judging History

This is the latest submission verdict.

  • [2024-05-29 13:33:40]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-05-29 13:33:39]
  • Submitted

answer

// Problem: undefined - THUPC 2024 Final J. 简单博弈
// Url: https://qoj.ac/contest/1691/problem/8748
// T/M Limit: 1000ms 1024MB
// Time: 2024-05-29 13:06:22
// Author: zjy0001

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define rep(Ii,Jj,Kk) for(int Ii=(Jj),Ii##_=(Kk);Ii<=Ii##_;Ii++)
#define per(Ii,Jj,Kk) for(int Ii=(Jj),Ii##_=(Kk);Ii>=Ii##_;Ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double db;
#define fir first
#define sec second
#define siz(Aa) ((int)(Aa).size())
#define all(Aa) (Aa).begin(),(Aa).end()
#define ckmx(Aa,Bb) (Aa=max(Aa,Bb))
#define ckmn(Aa,Bb) (Aa=min(Aa,Bb))

const int N=11,inf=1e9;
int f[8][N+1][N+1];
inline int mex(vector<int> v){
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	int x=0;
	while(x<siz(v) && v[x]==x) x++;
	return x;
}
int o(bool ty,int x){ return ty?x:inf; }
int F(int i,int j){
	if (i<j) swap(i,j);
	if (i%2==j%2) return i%2;
	return i%2+2;
}
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);
	rep(len,2,2*N) rep(i,1,N){
		int j=len-i;
		if(j<1 || j>N) continue;
		f[0][i][j]=mex({f[0][i-1][j],f[0][i][j-1],f[0][i-1][j-1]});
		f[1][i][j]=mex({
			o(i>=2				,f[1][i-1][j]),
			o(        j>=2		,f[1][i][j-1]),
			o(i>=2 && j>=2		,f[1][i-1][j-1]),
			o(        j>=2		,f[0][i-1][j]),
			o(i>=2				,f[0][i][j-1]),
			o(i>=2 || j>=2		,f[0][i-1][j-1])
		});	
		f[2][i][j]=mex({
			o(i>=2				,f[2][i-1][j]),
			o(        j>=3		,f[2][i][j-1]),
			o(i>=2 && j>=3		,f[2][i-1][j-1]),
			o(        j>=3		,f[0][i-1][j]),
			o(i>=2				,f[1][i][j-1]),
			o(i>=2 || j>=3		,f[0][i-1][j-1]),
			o(i>=2				,f[1][i-1][j-1])
		});
		f[3][i][j]=mex({
			o(i>=3				,f[3][i-1][j]),
			o(        j>=3		,f[3][i][j-1]),
			o(i>=3 && j>=3		,f[3][i-1][j-1]),
			f[1][i-1][j],
			f[1][i][j-1],
			f[1][i-1][j-1],
			f[0][i-1][j-1]
		});
		f[4][i][j]=mex({
			o(i>=2				,f[4][i-1][j]),
			o(        j>=4		,f[4][i][j-1]),
			o(i>=2 && j>=4		,f[4][i-1][j-1]),
			o(        j>=4		,f[0][i-1][j]),
			o(i>=2				,f[2][i][j-1]),
			o(i>=2 || j>=4		,f[0][i-1][j-1]),
			o(i>=2				,f[2][i-1][j-1])
		});
		f[5][i][j]=mex({
			o(i>=3				,f[5][i-1][j]),
			o(        j>=3		,f[5][i][j-1]),
			o(i>=3 && j>=3		,f[5][i-1][j-1]),
			o(        j>=3		,f[1][i-1][j]),
			f[2][i-1][j],
			o(i>=3				,f[1][i][j-1]),
			f[2][j-1][i],
			o(i>=3 || j>=3		,f[0][i-1][j-1]),
			f[1][i-1][j-1],
			o(        j>=3		,f[2][i-1][j-1]),
			o(i>=3				,f[2][j-1][i-1]),
		});
		f[6][i][j]=mex({
			o(i>=3				,f[6][i-1][j]),
			o(        j>=4		,f[6][i][j-1]),
			o(i>=3 && j>=4		,f[6][i-1][j-1]),
			f[1][i-1][j],
			f[2][i-1][j],
			f[3][i][j-1],
			f[2][i][j-1],
			f[0][i-1][j-1],
			f[1][i-1][j-1],
			f[2][i-1][j-1],
			o(i>=3				,f[3][i-1][j-1]),
		});
		f[7][i][j]=mex({
			o(i>=4				,f[7][i-1][j]),
			o(        j>=4		,f[7][i][j-1]),
			o(i>=4 && j>=4		,f[7][i-1][j-1]),
			f[3][i-1][j],
			f[3][i][j-1],
			f[1][i-1][j-1],
			f[3][i-1][j-1]
		});
	}
	rep(i,10,N) rep(j,10,i) rep(k,0,7)
	{
		if (i%2==j%2)
		{
			if (i%2==1) assert(f[k][i][j]==1);
			else assert(f[k][i][j]==0);
		}
		else
		{
			if (i%2==1) assert(f[k][i][j]==3);
			else assert(f[k][i][j]==2);
		}
	}
	int T,ans=0;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		vector<int> ox,oy;
		rep(i,1,3){
			int x,y;cin>>x>>y;
			ox.emplace_back(x);
			oy.emplace_back(y);
		}
		if (n>10&&m>10)
		{
			ans^=F(n,m);
			continue;
		}
		sort(all(ox)),ox.erase(unique(all(ox)),ox.end());
		sort(all(oy)),oy.erase(unique(all(oy)),oy.end());
		int x=siz(ox),y=siz(oy);
		if(x==3 && y==3) ans^=f[7][n][m];
		else if(x==2 && y==2) ans^=f[5][n][m];
		else if(x==1 && y==3) ans^=f[4][n][m];
		else if(x==3 && y==1) ans^=f[4][m][n];
		else if(x==2 && y==3) ans^=f[6][n][m];
		else if(x==3 && y==2) ans^=f[6][m][n];
	}
	cout<<(ans?"OvO\n":"QAQ\n");
return 0;}

詳細信息

Test #1:

score: 0
Runtime Error

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:


result: