QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#945001 | #10022. Jumping Game | Afterlife# | RE | 0ms | 3712kb | C++20 | 2.5kb | 2025-03-20 18:37:05 | 2025-03-20 18:37:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,m,id[505][505],c0,c1;
const int d[8][2]={
{1,2},
{2,1},
{-1,2},
{-2,1},
{1,-2},
{2,-1},
{-1,-2},
{-2,-1}
};
int g[N][N],match[N];
bool vis[N];
bool dfs(int u){
for(int i=1;i<=c1;++i){
if(g[u][i]){
if(vis[i])continue;
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=u;
return true;
}
}
}
return false;
}
int Match(){
for(int i=1;i<=c1;++i){
match[i]=0;
}
int ans=0;
for(int i=1;i<=c0;++i){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
return ans;
}
int x,y;
bool brute(){
c0=c1=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if((i+j)&1){
id[i][j]=++c1;
}
else{
id[i][j]=++c0;
}
}
}
for(int i=1;i<=c0;++i)
for(int j=1;j<=c1;++j)
g[i][j]=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if((i+j)%2==0){
for(int k=0;k<8;++k){
int ni=i+d[k][0];
int nj=j+d[k][1];
if(ni>=1&&ni<=n&&nj>=1&&nj<=m){
g[id[i][j]][id[ni][nj]]=1;
}
}
}
}
}
int pre=Match();
if((x+y)%2==0){
for(int j=1;j<=c1;++j){
g[id[x][y]][j]=0;
}
}
else{
for(int i=1;i<=c0;++i){
g[i][id[x][y]]=0;
}
}
return Match()!=pre;
}
bool Solve(){
cin>>n>>m>>x>>y;
//return brute();
if(n>m){
swap(x,y);
swap(n,m);
}
if(n==1){
return false;
}
if(n*m<=20){
return brute();
}
if(n==2){
if(m%4==0)return true;
else if(m%4==1){
if(y%4==1)return false;
else return true;
}
else if(m%4==2){
if(y%4==1||y%4==2)return false;
else return true;
}
else{
if(y%4==2)return false;
else return true;
}
}
if(n%2==0||m%2==0)return true;
return (x+y)&1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--){
cout<<(Solve()?"Annapurna\n":"Brahma\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
2 6 6 6 6 7 19 7 3
output:
Annapurna Brahma
result:
ok 2 tokens
Test #2:
score: -100
Runtime Error
input:
200000 652695136 300894239 597885661 210561036 360959967 978016924 93079366 526744440 466252780 624092439 424175327 115453901 16 16 10 10 14 19 12 2 281314939 780709721 243391639 329443634 22 15 9 3 17 19 5 10 19 25 17 1 715105073 886209327 453295637 441337663 18 23 5 2 7 21 3 20 25 23 7 1 21 23 10 ...