QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199384 | #7178. Bishops | kiwiHM# | WA | 248ms | 31792kb | C++14 | 2.2kb | 2023-10-04 11:00:03 | 2023-10-04 11:00:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node
{
int x,y;
friend bool operator < (node a,node b)
{
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
}an[1000010];
map<node,bool> mp;
inline void prin(int ans)
{
printf("%d\n",ans);
for(int i=1;i<=ans;i++)
printf("%d %d\n",an[i].x,an[i].y);
}
inline void W1(int i,int j)
{
int x=m+i-j;
if(x<=n&&x>=1) {mp[(node){x,m}]=1;return ;}
x=n-i+j;
if(x<=m&&x>=1) mp[(node){n,x}]=1;
}
inline void W2(int i,int j)
{
int x=i+j-1;
if(x<=n&&x>=1) {mp[(node){x,1}]=1;return ;}
x=i+j-n;
if(x<=m&&x>=1) mp[(node){n,x}]=1;
}
inline void W3(int i,int j)
{
int x=i+j-m;
if(x<=n&&x>=1) {mp[(node){x,m}]=1;return ;}
x=i+j-1;
if(x<=m&&x>=1) mp[(node){1,x}]=1;
}
inline void W4(int i,int j)
{
int x=i-j+1;
if(x<=n&&x>=1) {mp[(node){x,1}]=1;return ;}
x=1-i+j;
if(x<=m&&x>=1) mp[(node){1,x}]=1;
}
inline bool work(int x,int y,int &ans)
{
if(x<1||x>n) return 0;
if(y<1||y>m) return 0;
an[ans+1]=(node){x,y};
if(mp.find(an[ans+1])==mp.end())
{
ans++,mp[an[ans]]=1;
return 1;
}
return 0;
}
int main()
{
int ans=0;
scanf("%d%d",&n,&m);
if(n==1)
for(int i=1;i<=m;i++) an[++ans]=(node){1,i};
else if(m==1)
for(int i=1;i<=n;i++) an[++ans]=(node){i,1};
else
{
an[1]=(node){1,1},mp[an[1]]=1,ans++;
W1(an[1].x,an[1].y);
if(work(1,m,ans))
W2(an[2].x,an[2].y);
if(work(n,1,ans))
W3(an[3].x,an[3].y);
if(work(n,m,ans))
W4(an[4].x,an[4].y);
for(int i=2;i<=n||i<=m;i++)
{
if(work(1,i,ans)) W1(1,i),W2(1,i);
if(work(1,m-i+1,ans)) W1(1,m-i+1),W2(1,m-i+1);
if(work(i,1,ans)) W1(i,1),W3(i,1);
if(work(n-i+1,1,ans)) W1(n-i+1,1),W3(n-i+1,1);
if(work(n,i,ans)) W3(n,i),W4(n,i);
if(work(n,m-i+1,ans)) W3(n,m-i+1),W4(n,m-i+1);
if(work(i,m,ans)) W2(i,m),W4(i,m);
if(work(n-i+1,m,ans)) W2(n-i+1,m),W4(n-i+1,m);
}
}
prin(ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3828kb
input:
2 5
output:
6 1 1 1 5 2 1 2 5 1 3 2 3
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
5 5
output:
8 1 1 1 5 1 2 1 4 5 2 5 4 1 3 5 3
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 248ms
memory: 31108kb
input:
100000 100000
output:
199998 1 1 1 100000 1 2 1 99999 100000 2 100000 99999 1 3 1 99998 100000 3 100000 99998 1 4 1 99997 100000 4 100000 99997 1 5 1 99996 100000 5 100000 99996 1 6 1 99995 100000 6 100000 99995 1 7 1 99994 100000 7 100000 99994 1 8 1 99993 100000 8 100000 99993 1 9 1 99992 100000 9 100000 99992 1 10 1 9...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 246ms
memory: 31792kb
input:
100000 99999
output:
199998 1 1 1 99999 100000 1 100000 99999 1 2 1 99998 100000 2 100000 99998 1 3 1 99997 100000 3 100000 99997 1 4 1 99996 100000 4 100000 99996 1 5 1 99995 100000 5 100000 99995 1 6 1 99994 100000 6 100000 99994 1 7 1 99993 100000 7 100000 99993 1 8 1 99992 100000 8 100000 99992 1 9 1 99991 100000 9 ...
result:
ok n: 100000, m: 99999, bishops: 199998
Test #5:
score: -100
Wrong Answer
time: 136ms
memory: 24808kb
input:
100000 50000
output:
124999 1 1 1 50000 100000 1 100000 50000 1 2 1 49999 99999 1 100000 49999 1 3 1 49998 99998 1 100000 49998 1 4 1 49997 99997 1 100000 49997 1 5 1 49996 99996 1 100000 49996 1 6 1 49995 99995 1 100000 49995 1 7 1 49994 99994 1 100000 49994 1 8 1 49993 99993 1 100000 49993 1 9 1 49992 99992 1 100000 4...
result:
wrong answer Participant's answer is not optimal (124999 < 149998)