QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#442527 | #8748. 简单博弈 | Mindeveloped | TL | 0ms | 0kb | C++14 | 1.8kb | 2024-06-15 12:37:36 | 2024-06-15 16:48:00 |
Judging History
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";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
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 ...