QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#442531#8748. 简单博弈MindevelopedTL 0ms0kbC++141.8kb2024-06-15 12:38:022024-06-15 12:38:03

Judging History

This is the latest submission verdict.

  • [2024-06-15 12:38:03]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-06-15 12:38:02]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int f[505][505][1<<9];
int x[4],y[4];
vector<int> pos;
inline int ers1(int s,int x){
	for(int i=x;i<3;i++){
		s-=s&(1<<i),s-=s&(1<<(i+3)),s-=s&(1<<(i+6));
		s-=s&(1<<(i+1)),s-=s&(1<<(i+4)),s-=s&(1<<(i+7));
	}
	s|=(1<<2),s|=(1<<5),s|=(1<<8);
	return s;
}
inline int ers2(int s,int x){
	for(int i=x;i<3;i++){
		s-=s&(1<<i),s-=s&(1<<(i+1)),s-=s&(1<<(i+2));
		s-=s&(1<<(i+3)),s-=s&(1<<(i+4)),s-=s&(1<<(i+5));
	}
	s|=(1<<6),s|=(1<<7),s|=(1<<8);
	return s;
}
int main(){
	memset(f,-1,sizeof f);
	for(int i=0;i<=3;i++){
		for(int j=0;j<=3;j++){
			f[i][j][0]=0;
		}
	}
	for(int s=0;s<(1<<9);s++){
		int cnt=0;
		for(int d=0;d<9;d++){
			if(!(s&(1<<d))) cnt++;
		}
		if(cnt<=3){
			pos.push_back(s);
		}
	}
	for(int i=1;i<=500;i++){
		for(int j=1;j<=500;j++){
			for(int s:pos){
				//cout<<i<<" "<<j<<" "<<s<<"\n";
				if(f[i][j][s]!=-1) continue;
				int v=0;
				if(!f[i-1][j][s] || !f[i][j-1][s] || !f[i-1][j-1][s]){
					v=1;
				}
				for(int m=0;m<=2;m++){
					if(!f[i][j-1][ers1(s,m)]) v=1;
				}
				for(int n=0;n<=2;n++){
					if(!f[i-1][j][ers2(s,n)]) v=1;
				}
				for(int m=0;m<=2;m++){
					for(int n=0;n<=2;n++){
						if(!f[i-1][j-1][ers1(ers2(s,n),m)]) v=1;
					}
				}
				f[i][j][s]=v;
			}
		}
	}
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		int c1=0,c2=0;
		vector<int> v1,v2;
		map<int,int> id1,id2;
		for(int i=1;i<=3;i++){
			cin>>x[i]>>y[i];
			v1.push_back(x[i]);
			v2.push_back(y[i]);
		}
		sort(v1.begin(),v1.end());
		sort(v2.begin(),v2.end());
		for(int v:v1){
			if(!id1.count(v)) id1[v]=c1++;
		}
		for(int v:v2){
			if(!id2.count(v)) id2[v]=c2++;
		}
		int ns=(1<<10)-1;
		for(int i=1;i<=3;i++){
			ns^=(1<<(id1[x[i]]*3+id2[y[i]]));
		}
		if(f[n][m][ns]){
			cout<<"OvO\n";
		}
		else{
			cout<<"QAQ\n";
		}
	}
} 

详细

Test #1:

score: 0
Time Limit Exceeded

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: