QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#199384#7178. BishopskiwiHM#WA 248ms31792kbC++142.2kb2023-10-04 11:00:032023-10-04 11:00:03

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 11:00:03]
  • 评测
  • 测评结果:WA
  • 用时:248ms
  • 内存:31792kb
  • [2023-10-04 11:00:03]
  • 提交

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);
}

详细

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)