QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#433069 | #8748. 简单博弈 | LiWenX# | AC ✓ | 334ms | 16040kb | C++20 | 3.0kb | 2024-06-07 23:36:18 | 2024-06-07 23:36:19 |
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<(int)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))
int 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==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==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(y-1,x,2);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(y-1,x-1,2);
if(y>2) lf(x,y-1,7),lf(x-1,y-1,1),lf(y-1,x-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==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;
for(int i=1;i<=3;i++) cin>>x[i]>>y[i];
int num1=0,num2=0;
for(int i=1;i<=3;i++){
for(int j=i+1;j<=3;j++){
num1+=(x[i]==x[j]);
num2+=(y[i]==y[j]);
}
}if(num1==3) num1--;if(num2==3) num2--;
num1=3-num1,num2=3-num2;
if(num1>num2){
swap(num1,num2);
swap(n,m);
}
int ans=0;
if(num1==1&&num2==3){
ans=dfs(n,m,5);
}
else if(num1==2&&num2==2){
ans=dfs(n,m,7);
}
else if(num1==2&&num2==3){
ans=dfs(n,m,8);
}
else ans=dfs(n,m,10);
ALL^=ans;
}
signed main(){
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: 317ms
memory: 15792kb
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: 311ms
memory: 15816kb
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: 323ms
memory: 15708kb
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: 0
Accepted
time: 302ms
memory: 15780kb
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:
QAQ
result:
ok single line: 'QAQ'
Test #5:
score: 0
Accepted
time: 313ms
memory: 15720kb
input:
100000 446 178 5 66 276 167 380 142 4 156 1 148 1 2 4 94 58 309 8 288 19 215 51 258 3 4 1 2 3 3 2 1 297 4 221 2 290 2 65 3 130 4 20 3 40 1 56 1 226 383 105 140 178 189 209 5 4 1 3 1 4 1 2 1 182 493 12 215 56 189 50 34 102 1 95 1 89 1 48 1 305 145 237 61 6 55 300 117 383 468 175 318 359 112 204 196 3...
output:
OvO
result:
ok single line: 'OvO'
Test #6:
score: 0
Accepted
time: 324ms
memory: 15780kb
input:
100000 281 285 167 24 190 98 212 189 310 1 134 1 140 1 123 1 92 90 50 28 23 52 42 41 171 1 54 1 114 1 10 1 3 1 1 1 2 1 3 1 483 272 114 80 284 209 399 180 4 4 3 4 3 1 1 3 240 19 117 14 166 13 231 11 445 55 172 24 238 2 249 3 283 2 217 1 74 2 87 2 314 343 231 322 302 226 310 68 260 323 231 82 233 193 ...
output:
QAQ
result:
ok single line: 'QAQ'
Test #7:
score: 0
Accepted
time: 321ms
memory: 15756kb
input:
100000 2 433 1 289 2 338 2 143 19 18 14 17 12 12 2 6 4 125 1 78 1 105 1 10 397 21 76 21 62 1 71 11 1 4 1 3 1 2 1 4 4 4 3 4 2 3 4 1 3 2 2 1 1 1 1 2 76 79 25 49 55 62 68 29 455 455 40 19 170 5 245 187 18 390 16 41 18 178 18 241 4 2 1 1 1 2 3 1 3 473 1 41 2 127 1 196 351 3 112 3 201 3 149 2 3 258 3 210...
output:
OvO
result:
ok single line: 'OvO'
Test #8:
score: 0
Accepted
time: 304ms
memory: 15756kb
input:
100000 235 235 86 155 200 12 84 226 349 462 284 345 342 81 344 386 336 170 249 47 283 136 295 20 318 158 5 28 189 19 111 77 124 486 59 227 90 161 106 184 447 207 446 103 136 77 5 85 209 210 158 105 34 160 80 146 103 355 91 187 95 207 99 137 221 3 194 1 147 1 68 3 204 50 36 13 197 12 202 8 3 2 3 2 3 ...
output:
QAQ
result:
ok single line: 'QAQ'
Test #9:
score: 0
Accepted
time: 320ms
memory: 15708kb
input:
100000 16 241 14 137 8 33 5 97 351 301 23 121 143 19 329 20 2 4 2 1 2 2 1 2 325 182 160 152 297 106 241 98 3 255 3 200 1 131 3 93 3 2 2 1 1 1 3 2 4 1 1 1 4 1 3 1 311 88 152 32 157 81 251 13 232 234 92 35 229 64 32 17 1 3 1 3 1 1 1 2 338 467 33 142 31 435 194 166 161 425 154 150 2 374 74 112 132 132 ...
output:
OvO
result:
ok single line: 'OvO'
Test #10:
score: 0
Accepted
time: 282ms
memory: 15692kb
input:
100000 3 2 3 2 2 2 2 1 276 4 46 2 152 2 60 2 3 2 3 1 1 2 3 2 106 105 13 62 71 14 71 57 182 369 86 110 92 205 45 60 305 4 305 1 22 2 290 2 2 296 1 47 1 292 1 285 72 1 35 1 52 1 43 1 321 4 166 3 319 4 112 1 1 82 1 82 1 41 1 49 129 206 34 107 91 78 97 183 2 2 2 2 1 1 2 1 319 402 179 128 251 194 302 202...
output:
QAQ
result:
ok single line: 'QAQ'
Test #11:
score: 0
Accepted
time: 332ms
memory: 15992kb
input:
100000 288 287 230 175 194 262 41 63 319 465 5 393 213 412 305 317 2 327 2 113 2 149 1 69 309 421 207 364 220 56 293 392 160 20 109 9 152 9 154 11 64 66 38 14 21 26 29 42 336 393 7 287 154 343 317 222 231 4 94 1 177 2 53 3 2 4 1 1 2 2 1 4 237 235 115 151 57 88 64 47 3 432 2 44 2 398 2 404 59 29 1 9 ...
output:
OvO
result:
ok single line: 'OvO'
Test #12:
score: 0
Accepted
time: 308ms
memory: 15772kb
input:
100000 269 123 178 66 117 84 17 9 3 40 3 25 2 32 3 15 2 140 2 45 1 66 2 59 243 178 66 58 45 77 110 91 147 1 56 1 48 1 137 1 72 165 29 99 67 145 10 5 2 2 1 1 1 2 2 1 4 91 2 9 1 81 2 23 484 2 417 1 416 2 55 2 70 69 63 40 65 56 57 22 83 202 16 27 22 139 43 102 196 2 43 1 23 2 31 1 467 8 447 4 21 5 266 ...
output:
QAQ
result:
ok single line: 'QAQ'
Test #13:
score: 0
Accepted
time: 314ms
memory: 15784kb
input:
100000 3 209 3 95 1 27 3 125 264 450 260 265 263 169 264 371 3 106 1 41 2 98 3 8 2 500 2 76 2 336 2 145 1 193 1 54 1 187 1 2 2 4 2 1 1 4 1 1 171 415 54 87 67 66 163 340 4 3 2 2 2 3 2 1 39 72 14 11 11 25 39 55 1 3 1 2 1 3 1 1 7 1 5 1 1 1 4 1 165 1 101 1 157 1 9 1 245 2 210 1 163 2 40 1 380 497 259 31...
output:
OvO
result:
ok single line: 'OvO'
Test #14:
score: 0
Accepted
time: 312ms
memory: 15796kb
input:
100000 72 496 72 285 72 401 72 477 1 31 1 15 1 13 1 1 349 4 331 4 219 2 38 3 2 4 2 2 2 3 1 2 123 123 48 63 115 34 71 72 351 303 114 52 302 180 339 146 449 480 439 176 447 443 449 338 2 284 1 111 2 248 2 103 184 355 159 50 169 206 180 282 3 292 1 199 3 97 2 266 117 4 38 4 24 3 50 3 31 3 5 2 9 1 10 2 ...
output:
QAQ
result:
ok single line: 'QAQ'
Test #15:
score: 0
Accepted
time: 334ms
memory: 16040kb
input:
100000 315 3 107 3 306 2 171 2 2 2 2 1 2 2 1 2 1 373 1 234 1 178 1 360 4 38 3 9 3 8 3 1 12 485 8 87 8 474 10 479 3 263 2 231 2 34 3 253 2 446 1 195 2 102 1 408 92 285 27 79 30 125 92 17 55 4 26 1 34 4 40 2 3 286 2 20 1 163 2 132 67 295 63 101 64 265 65 104 316 318 82 5 37 304 258 223 2 197 1 38 2 46...
output:
OvO
result:
ok single line: 'OvO'
Test #16:
score: 0
Accepted
time: 297ms
memory: 15936kb
input:
100000 378 4 124 4 239 3 14 2 54 52 15 2 50 21 23 8 275 275 36 186 272 191 180 175 217 309 164 6 173 301 200 189 69 1 23 1 65 1 32 1 4 3 1 2 3 2 3 1 271 271 252 3 54 16 124 5 184 2 162 1 56 1 74 1 94 3 50 2 33 1 16 1 176 4 11 4 12 1 7 3 358 414 2 320 40 129 317 289 102 333 30 209 38 200 46 219 290 2...
output:
QAQ
result:
ok single line: 'QAQ'
Test #17:
score: 0
Accepted
time: 323ms
memory: 15880kb
input:
100000 1 3 1 2 1 1 1 3 15 17 12 17 6 9 2 7 474 473 240 285 451 273 248 51 414 1 178 1 10 1 167 1 100 2 1 2 56 2 28 1 2 343 2 276 1 136 2 98 2 332 2 148 1 80 1 45 1 4 1 4 1 2 1 1 280 4 13 1 50 2 260 2 254 29 78 27 209 3 10 24 261 3 219 2 64 2 21 1 4 4 3 2 2 1 2 4 3 3 2 3 1 2 1 1 138 387 69 337 11 223...
output:
OvO
result:
ok single line: 'OvO'
Test #18:
score: 0
Accepted
time: 310ms
memory: 15692kb
input:
100000 3 129 1 63 3 118 3 18 39 2 34 2 36 2 23 2 1 192 1 15 1 161 1 97 64 62 62 60 62 13 61 2 408 2 150 2 260 2 210 2 395 393 299 87 388 208 76 256 3 4 2 4 1 1 1 4 1 432 1 33 1 72 1 119 4 1 4 1 1 1 2 1 294 3 24 3 133 1 222 2 135 441 16 180 96 121 98 121 269 146 228 94 60 103 147 146 468 3 332 1 419 ...
output:
QAQ
result:
ok single line: 'QAQ'
Test #19:
score: 0
Accepted
time: 331ms
memory: 15816kb
input:
100000 398 397 216 140 299 394 152 336 3 498 3 248 3 276 3 23 35 398 7 173 34 370 9 121 450 496 214 182 221 336 400 234 427 2 192 1 287 1 271 1 483 296 257 29 422 44 474 233 3 1 3 1 2 1 1 1 355 355 21 18 237 195 134 330 380 458 35 18 1 17 159 443 2 120 1 12 2 73 1 20 79 311 33 308 52 201 73 58 3 1 2...
output:
OvO
result:
ok single line: 'OvO'
Test #20:
score: 0
Accepted
time: 294ms
memory: 15776kb
input:
100000 472 470 21 286 207 110 374 189 4 88 1 72 2 35 2 58 186 338 95 164 186 5 186 168 132 489 33 1 77 256 87 3 4 2 1 2 4 2 3 2 455 301 208 125 207 93 386 250 319 31 170 30 78 11 149 18 4 4 3 3 1 2 3 4 2 479 2 204 1 61 1 150 3 1 3 1 1 1 2 1 4 271 2 137 4 111 3 117 2 3 1 3 1 1 2 3 362 473 324 234 328...
output:
QAQ
result:
ok single line: 'QAQ'