QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#426477 | #8748. 简单博弈 | ucup-team1004 | WA | 1460ms | 24692kb | C++14 | 4.8kb | 2024-05-31 12:32:53 | 2024-05-31 12:32:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),x.end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<class S,class T>
ostream& operator << (ostream &out,pair<S,T> a);
template<class T>
ostream& operator << (ostream &out,vector<T> a);
template<class...T>
ostream& operator << (ostream &out,tuple<T...> a);
#ifdef DEBUG
template<class T>
void debug(T x);
template<class T,class...S>
void debug(T x,S...y);
#else
#define debug(...) void()
#endif
using ll=long long;
using ull=unsigned long long;
const int N=5e2+10;
int T,n,m,x[3],y[3];
int mex(vector<int>a){
sort(all(a));
a.erase(unique(all(a)),a.end());
int res=0;
for(;res<a.size()&&a[res]==res;res++);
return res;
}
const int M=20;
int f[M][N][N];
using state=array<array<int,4>,4>;
state I;
ostream& operator << (ostream &out,array<int,4> a){
out<<'[';
for(auto x:a)out<<x<<',';
return out<<']';
}
ostream& operator << (ostream &out,state a){
out<<'[';
for(auto x:a)out<<x<<',';
return out<<']';
}
map<state,int>trs;
state cur[M];
int his[1<<9];
int find(state a){
int S=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
S=S<<1|a[i][j];
}
}
if(~his[S])return his[S];
state las=a;
array<int,4>p,q;
iota(all(p),0);
do{
iota(all(q),0);
do{
state b;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
b[p[i]][q[j]]=las[i][j];
}
}
a=min(a,b);
}while(next_permutation(q.begin(),q.begin()+3));
}while(next_permutation(p.begin(),p.begin()+3));
if(trs.count(a))return his[S]=trs[a];
int id=trs.size();
// debug(id,a);
return cur[id]=a,his[S]=trs[a]=id;
}
int dfs(int op,int n,int m){
// debug(op,n,m);
if(~f[op][n][m])return f[op][n][m];
if(min(n,m)<1)return 0;
state p=cur[op],q=p;
for(int i=0;i<4;i++){
for(int j=0;j<i;j++)swap(q[i][j],q[j][i]);
}
array<int,4>s,t;
s.fill(0),t.fill(0);
for(int i=0;i<min(n,4);i++){
for(int j=0;j<min(m,4);j++){
if(!p[i][j])s[i]=t[j]=1;
}
}
vector<int>res;
for(int i=0;i<min(n,4);i++)if(s[i]){
if(i&&p[i]==p[i-1])continue;
state ne=I;
for(int x=0;x<min(n,4);x++)if(x^i){
for(int y=0;y<min(m,4);y++){
ne[x-(x>i)][y]=p[x][y];
}
}
res.push_back(dfs(find(ne),n-1,m));
}
for(int j=0;j<min(m,4);j++)if(t[j]){
if(j&&q[j]==q[j-1])continue;
state ne=I;
for(int x=0;x<min(n,4);x++){
for(int y=0;y<min(m,4);y++)if(y^j){
ne[x][y-(y>j)]=p[x][y];
}
}
res.push_back(dfs(find(ne),n,m-1));
}
for(int i=0;i<min(n,4);i++){
if(i&&p[i]==p[i-1])continue;
for(int j=0;j<min(m,4);j++){
if(j&&q[j]==q[j-1])continue;
if(!s[i]&&!t[j])continue;
state ne=I;
for(int x=0;x<min(n,4);x++)if(x^i){
for(int y=0;y<min(m,4);y++)if(y^j){
ne[x-(x>i)][y-(y>j)]=p[x][y];
}
}
res.push_back(dfs(find(ne),n-1,m-1));
}
}
return f[op][n][m]=mex(res);
}
void init(int n=N-1){
memset(his,-1,sizeof his);
memset(f,-1,sizeof f);
// state a;
// a=I;
// a[0][0]=a[1][1]=a[2][2]=1;
// int u=find(a);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// dfs(u,i,j);
// }
// }
// // debug("OK");
// a[2][2]=0,a[1][2]=1;
// u=find(a);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// dfs(u,i,j);
// }
// }
// a=I;
// a[0][0]=a[0][1]=a[1][0]=1;
// u=find(a);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// dfs(u,i,j);
// }
// }
// a=I;
// a[0][0]=a[0][1]=a[0][2]=1;
// u=find(a);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// dfs(u,i,j);
// }
// }
}
void reduce(int *x){
vector<int>nx{x,x+3};
sort(all(nx)),nx.erase(unique(all(nx)),nx.end());
for(int i=0;i<3;i++)x[i]=lower_bound(all(nx),x[i])-nx.begin();
}
void get(){
cin>>n>>m;
for(int i=0;i<3;i++){
cin>>x[i]>>y[i];
}
reduce(x),reduce(y);
state a=I;
for(int i=0;i<3;i++)a[x[i]][y[i]]=1;
puts(dfs(find(a),n,m)?"OvO":"QAQ");
}
void clr(){}
template<bool x>
using If=typename enable_if<x>::type;
template<int i,class T>
If<i==0> otp(ostream &out,T a){
out<<get<i>(a);
}
template<int i,class T>
If<i!=0> otp(ostream &out,T a){
otp<i-1>(out,a),out<<','<<get<i>(a);
}
template<class...T>
ostream& operator << (ostream &out,tuple<T...> a){
return out<<'(',otp<sizeof...(T)-1>(out,a),out<<')';
}
template<class S,class T>
ostream& operator << (ostream &out,pair<S,T> a){
return out<<'('<<a.first<<','<<a.second<<')';
}
template<class T>
ostream& operator << (ostream &out,vector<T> a){
out<<'[';
for(auto x:a)out<<x<<',';
return out<<']';
}
#ifdef DEBUG
template<class T>
void debug(T x){
cerr<<x<<endl;
}
template<class T,class...S>
void debug(T x,S...y){
cerr<<x<<' ',debug(y...);
}
#endif
int main(){
int T;
scanf("%d",&T);
for(init();T--;clr())get();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1460ms
memory: 24692kb
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 OvO OvO QAQ OvO QAQ QAQ OvO OvO QAQ QAQ OvO OvO QAQ OvO OvO OvO QAQ OvO OvO OvO OvO OvO OvO QAQ OvO OvO OvO QAQ OvO OvO QAQ QAQ OvO OvO OvO OvO OvO QAQ OvO OvO QAQ QAQ OvO QAQ OvO OvO OvO OvO OvO QAQ OvO OvO OvO OvO QAQ QAQ QAQ OvO OvO QAQ OvO QAQ OvO OvO QAQ OvO OvO OvO OvO OvO OvO QAQ OvO OvO ...
result:
wrong output format Extra information in the output file