QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #442617 | #8748. 简单博弈 | union_of_britain# | WA | 858ms | 122644kb | C++14 | 4.2kb | 2024-06-15 13:02:20 | 2024-06-15 13:02:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define VI vector<int>
int f[505][505][8][8];
inline int mex(const VI &V){
int vis[10];
for(int i=0;i<10;i++)vis[i]=0;
for(auto u:V)if(u<10)vis[u]=1;
int res=0;
for(;vis[res];++res);
// for(auto u:V)cout<<u<<" ";
// cout<<endl;
// cout<<"res="<<res<<endl;
return res;
}
int N=500;
int SW(int S,int x,int y){
S=S+(((S>>x)&1)<<y)+(((S>>y)&1)<<x)-(((S>>x)&1)<<x)-(((S>>y)&1)<<y);
return S;
}
void getS(int &x,int &y){
if(x==2){
SW(x,0,1);SW(y,0,1);
}else if(x==4){
SW(x,0,2);SW(y,0,2);
}else if(x==6){
SW(x,0,2);SW(y,0,2);
}else if(x==5){
SW(x,2,1);SW(y,2,1);
}
}
pair<int,int> gs[8][8];
int f2[505][505][8][4],f4[505][505][4][4],f5[505][505][4][2];
signed main(){
for(int i=0;i<8;i++)for(int j=0;j<8;j++){
int x=i,y=j;getS(x,y);
gs[i][j]={x,y};
}
for(int n=0;n<=N;n++){
for(int m=0;m<=N;m++){
for(int S1=7;S1>=0;S1--){
for(int S2=7;S2>=0;S2--){
if(make_pair(S1,S2)!=gs[S1][S2])continue;
VI V(8,114513);
if(n>0&&(S2!=7||m>0))V[0]=f[n-1][m][S1][S2];
if(m>0&&(S1!=7||n>0))V[1]=f[n][m-1][S1][S2];
if(!(S1&1)&&!(m==0&&(S2&2)&&(S2&4)))V[2]=f[n][m][gs[S1|1][S2].first][gs[S1|1][S2].second];
if(!(S2&1)&&!(n==0&&(S1&2)&&(S1&4)))V[3]=f[n][m][gs[S1][S2|1].first][gs[S1][S2|1].second];
if(!(S1&2)&&!(m==0&&(S2&1)&&(S2&4)))V[4]=f[n][m][gs[S1|2][S2].first][gs[S1|2][S2].second];
if(!(S2&2)&&!(n==0&&(S1&1)&&(S1&4)))V[5]=f[n][m][gs[S1][S2|2].first][gs[S1][S2|2].second];
if(!(S1&4)&&!(m==0&&(S2&1)&&(S2&2)))V[6]=f[n][m][gs[S1|4][S2].first][gs[S1|4][S2].second];
if(!(S2&4)&&!(n==0&&(S1&1)&&(S1&2)))V[7]=f[n][m][gs[S1][S2|4].first][gs[S1][S2|4].second];
f[n][m][S1][S2]=mex(V);
}
}
}
}
for(int n=0;n<=N;n++){
for(int m=0;m<=N;m++){
for(int S1=3;S1>=0;S1--){
for(int S2=7;S2>=0;S2--){
if(make_pair(S1,S2)!=gs[S1][S2])continue;
VI V(7,114513);
if(n>0&&(S2!=7||m>0))V[0]=f2[n-1][m][S1][S2];
if(m>0&&(S1!=3||n>0))V[1]=f2[n][m-1][S1][S2];
if(!(S1&1)&&!(m==0&&(S2&2)))V[2]=f2[n][m][gs[S1|1][S2].first][gs[S1|1][S2].second];
if(!(S2&1)&&!(n==0&&(S1&2)))V[3]=f2[n][m][gs[S1][S2|1].first][gs[S1][S2|1].second];
if(!(S1&2)&&!(m==0&&(S2&1)&&(S2&4)))V[4]=f2[n][m][gs[S1|2][S2].first][gs[S1|2][S2].second];
if(!(S2&2)&&!(n==0&&(S1&1)))V[5]=f2[n][m][gs[S1][S2|2].first][gs[S1][S2|2].second];
if(!(S2&4)&&!(n==0&&(S1&1)))V[6]=f2[n][m][gs[S1][S2|4].first][gs[S1][S2|4].second];
f2[n][m][S1][S2]=mex(V);
}
}
}
}
for(int n=0;n<=N;n++){
for(int m=0;m<=N;m++){
for(int S1=3;S1>=0;S1--){
for(int S2=3;S2>=0;S2--){
if(make_pair(S1,S2)!=gs[S1][S2])continue;
VI V(6,114513);
if(n>0&&(S2!=3||m>0))V[0]=f4[n-1][m][S1][S2];
if(m>0&&(S1!=3||n>0))V[1]=f4[n][m-1][S1][S2];
if(!(S1&1)&&!(m==0&&(S2&2)))V[2]=f4[n][m][gs[S1|1][S2].first][gs[S1|1][S2].second];
if(!(S2&1)&&!(n==0))V[3]=f4[n][m][gs[S1][S2|1].first][gs[S1][S2|1].second];
if(!(S1&2)&&!(m==0))V[4]=f4[n][m][gs[S1|2][S2].first][gs[S1|2][S2].second];
if(!(S2&2)&&!(n==0&&(S1&1)))V[5]=f4[n][m][gs[S1][S2|2].first][gs[S1][S2|2].second];
f4[n][m][S1][S2]=mex(V);
}
}
}
}
for(int n=0;n<=N;n++){
for(int m=0;m<=N;m++){
for(int S1=3;S1>=0;S1--){
for(int S2=1;S2>=0;S2--){
VI V(4,114513);
if(n>0&&(S2!=3||m>0))V[0]=f5[n-1][m][S1][S2];
if(m>0&&(S1!=1||n>0))V[1]=f5[n][m-1][S1][S2];
if(S1<3&&(m>0))V[2]=f5[n][m][S1+1][S2];
if(S2<1&&(S1<3||m>0))V[3]=f5[n][m][S1][S2+1];
f5[n][m][S1][S2]=mex(V);
}
}
}
}
int n,r=0,m,k;
cin>>k;
while(k--){
cin>>n>>m;
int x[3],y[3];
set<int> xi,yi;
for(int i=0;i<3;i++){
cin>>x[i]>>y[i];
xi.insert(x[i]),yi.insert(y[i]);
}
if(xi.size()==3&&yi.size()==3){
r^=f[n-3][m-3][0][0];
}if(xi.size()==3&&yi.size()==2){
r^=f2[n-3][m-2][0][0];
}if(xi.size()==2&&yi.size()==3){
r^=f2[m-3][n-2][0][0];
}if(xi.size()==2&&yi.size()==2){
r^=f4[n-2][m-2][0][0];
}if(xi.size()==3&&yi.size()==1){
r^=f5[n-3][m-1][0][0];
}if(xi.size()==1&&yi.size()==3){
r^=f5[m-3][n-1][0][0];
}
}
if(r)cout<<"OvO"<<endl;
else cout<<"QAQ"<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 843ms
memory: 122644kb
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: 848ms
memory: 122580kb
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: 858ms
memory: 122636kb
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: 856ms
memory: 122580kb
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'