QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#424583 | #8748. 简单博弈 | ShaojiaZhang | WA | 43ms | 3864kb | C++17 | 3.7kb | 2024-05-29 13:37:25 | 2024-05-29 13:37:25 |
Judging History
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]
});
}
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;
}
if (n>m)
{
int d=(n-m)/2*2;
n-=d;
}
else if (m>n)
{
int d=(m-n)/2*2;
m-=d;
}
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: 100
Accepted
time: 43ms
memory: 3596kb
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: 39ms
memory: 3864kb
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: 43ms
memory: 3560kb
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: 43ms
memory: 3572kb
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: 43ms
memory: 3572kb
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: -100
Wrong Answer
time: 38ms
memory: 3508kb
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:
OvO
result:
wrong answer 1st lines differ - expected: 'QAQ', found: 'OvO'