QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#433064 | #8748. 简单博弈 | LiWenX# | WA | 335ms | 16012kb | C++20 | 3.2kb | 2024-06-07 23:27:25 | 2024-06-07 23:27:27 |
Judging History
answer
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=500;
int f[N+5][N+5][12];
vector<int> vec;
int n,m,x[4],y[4];
int mex(vector<int> vec){
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
// for(int u:vec) cout<<u<<" ";
for(int i=0;i<vec.size();i++){
if(vec[i]!=i){
// cout<<i<<'\n';
return i;
}
}return vec.size();
}
#define lf(x,y,z) vec.push_back(dfs(x,y,z))
bool dfs(int x,int y,int id){
if(f[x][y][id]!=-1) return f[x][y][id];
// cout<<x<<" "<<y<<" "<<id<<'\n' ;
// if(x<0||y<0) cout<<x<<" "<<y<<" "<<id<<'\n';
if(!x||!y) return 0;
vector<int> vec;
if(id==0){
lf(x-1,y,0);lf(x,y-1,0);lf(x-1,y-1,0);
}
if(id==1){
if(x==1) return dfs(x,y-1,0);
if(y==1) return dfs(x-1,y,0);
lf(x-1,y,0);lf(x,y-1,0);lf(x-1,y-1,0);
if(x>1) lf(x-1,y,1);
if(y>1) lf(x,y-1,1);
if(x>1&&y>1) lf(x-1,y-1,1);
}
if(id==2){
if(y==2) return dfs(x-1,y,0);
if(x==1) return dfs(x,y-2,0);
lf(x-1,y,0);lf(x,y-1,1);lf(x-1,y-1,0);
if(x>1) lf(x-1,y,2),lf(x-1,y-1,1);
if(y>2) lf(x,y-1,2);
if(x>1&&y>2) lf(x-1,y-1,2);
}
if(id==3){
return dfs(y,x,2);
}
if(id==4){
lf(x-1,y,1);lf(x,y-1,1);lf(x-1,y-1,1);lf(x-1,y-1,0);
if(x>2) lf(x-1,y,4),lf(x-1,y-1,1);
if(y>2) lf(x,y-1,4),lf(x-1,y-1,1);
if(x>2&&y>2) lf(x-1,y-1,4);
}
if(id==5){
// if(y<3) cout<<x<<" "<<y<<'\n';
if(y==3) return dfs(x-1,y,0);
if(x==1) return dfs(x,y-3,0);
lf(x-1,y,0);lf(x,y-1,2);lf(x-1,y-1,0);
if(x>1) lf(x-1,y,5),lf(x-1,y-1,2);
if(y>3) lf(x,y-1,5);
if(x>1&&y>3) lf(x-1,y-1,5);
}
if(id==6){
// if(x<3) cout<<'*';
return dfs(y,x,5);
}
if(id==7){
if(x==2) return dfs(x,y-1,1);
if(y==2) return dfs(x-1,y,1);
lf(x-1,y,1);lf(x-1,y,2);lf(x,y-1,1);lf(x,y-1,3);lf(x-1,y-1,0);lf(x-1,y-1,1);
if(x>2) lf(x-1,y,7),lf(x-1,y-1,1),lf(x-1,y-1,3);
if(y>2) lf(x,y-1,7),lf(x-1,y-1,1),lf(x-1,y-1,2);
if(x>2&&y>2) lf(x-1,y-1,7);
}
if(id==8){
lf(x-1,y,1);lf(x-1,y,2);lf(x,y-1,4),lf(x,y-1,2);
lf(x-1,y-1,1);lf(x-1,y-1,0);lf(x-1,y-1,2);
if(x>2) lf(x-1,y,8),lf(x-1,y-1,4),lf(x-1,y-1,2);
if(y>3) lf(x,y-1,8),lf(x-1,y-1,1),lf(x-1,y-1,2);
if(x>2&&y>3) lf(x-1,y-1,8);
}
if(id==9){
return dfs(y,x,8);
}
if(id==10){
lf(x-1,y,4);lf(x,y-1,4);lf(x-1,y-1,4);lf(x-1,y-1,1);
if(x>3) lf(x-1,y,10),lf(x-1,y-1,4);
if(y>3) lf(x,y-1,10),lf(x-1,y-1,4);
if(x>3&&y>3) lf(x-1,y-1,10);
}
f[x][y][id]=mex(vec);
return f[x][y][id];
}
int ALL;
void solve(){
cin>>n>>m;
set<int> X,Y;
for(int i=1;i<=3;i++) cin>>x[i]>>y[i],X.insert(x[i]),Y.insert(y[i]);
int num1=X.size(),num2=Y.size();
// if(num1<num2){
// swap(num1,num2);
// swap(n,m);
// }
bool ans=0;
if(num1==1&&num2==3){
ans=dfs(n,m,5);
}
else if(num1==3&&num2==1){
ans=dfs(n,m,6);
}
else if(num1==2&&num2==2){
ans=dfs(n,m,7);
}
else if(num1==2&&num2==3){
ans=dfs(n,m,8);
}
else if(num1==3&&num2==2){
ans=dfs(n,m,9);
}
else ans=dfs(n,m,10);
ALL^=ans;
}
signed main(){
// freopen("P10549_1.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(f,-1,sizeof(f));
int tt;cin>>tt;
while(tt--) solve();
if(ALL) cout<<"OvO";
else cout<<"QAQ";
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 321ms
memory: 15716kb
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: 0
Accepted
time: 320ms
memory: 15832kb
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:
QAQ
result:
ok single line: 'QAQ'
Test #3:
score: 0
Accepted
time: 335ms
memory: 16012kb
input:
100000 91 476 28 345 28 379 20 119 4 3 4 1 1 2 4 3 117 77 33 74 92 38 102 26 2 3 2 2 1 1 1 3 443 3 252 1 305 3 106 1 410 3 156 3 380 3 135 2 222 275 135 223 181 134 53 241 106 105 100 32 92 27 44 88 140 267 112 129 129 194 133 234 3 489 2 2 3 267 2 9 1 410 1 348 1 315 1 119 101 102 71 73 44 61 56 55...
output:
OvO
result:
ok single line: 'OvO'
Test #4:
score: -100
Wrong Answer
time: 313ms
memory: 15704kb
input:
100000 1 256 1 254 1 90 1 39 4 373 2 6 4 365 3 265 229 2 67 2 2 1 100 2 130 129 102 57 22 82 20 29 1 4 1 1 1 2 1 3 3 2 1 1 2 2 1 2 415 384 109 278 281 175 285 182 2 455 1 196 1 221 1 335 108 385 82 145 108 143 34 57 369 260 361 226 365 124 369 182 3 2 1 1 3 2 1 2 13 3 12 3 3 3 2 1 4 2 3 2 3 1 2 2 40...
output:
OvO
result:
wrong answer 1st lines differ - expected: 'QAQ', found: 'OvO'