QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199458#7178. BishopskiwiHM#WA 415ms65660kbC++144.0kb2023-10-04 12:25:162023-10-04 12:25:17

Judging History

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

  • [2023-10-04 12:25:17]
  • 评测
  • 测评结果:WA
  • 用时:415ms
  • 内存:65660kb
  • [2023-10-04 12:25:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,du[1000010];
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],re[1000010];
vector<node> v[1000010];
set<pair<int,int> >s;
map<node,int> 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 node W1(int i,int j)
{
    int x=m+i-j;
    if(x<=n&&x>=1) {mp[(node){x,m}]=1;return (node){x,m};}
    x=n-i+j;
    if(x<=m&&x>=1) {mp[(node){n,x}]=1;return (node){n,x};}
    return (node){0,0};
}
inline node W2(int i,int j)
{
    int x=i+j-1;
    if(x<=n&&x>=1) {mp[(node){x,1}]=1;return (node){x,1};}
    x=i+j-n;
    if(x<=m&&x>=1) {mp[(node){n,x}]=1;return (node){n,x};}
    return (node){0,0};
}
inline node W3(int i,int j)
{
    int x=i+j-m;
    if(x<=n&&x>=1) {mp[(node){x,m}]=1;return (node){x,m};}
    x=i+j-1;
    if(x<=m&&x>=1) {mp[(node){1,x}]=1;return (node){1,x};}
    return (node){0,0};
}
inline node W4(int i,int j)
{
    int x=i-j+1;
    if(x<=n&&x>=1) {mp[(node){x,1}]=1;return (node){x,1};}
    x=1-i+j;
    if(x<=m&&x>=1) {mp[(node){1,x}]=1;return (node){1,x};}
    return (node){0,0};
}
inline bool work(int x,int y,int cur)
{
    if(x<1||x>n) return 0;
    if(y<1||y>m) return 0;
    if(mp.find((node){x,y})!=mp.end())
        return 0;
    mp[(node){x,y}]=cur;
    return 1;
}
inline void id(int x,int y,int &cur,int op)
{
    if(!work(x,y,cur+1)) return ;
    re[++cur]=(node){x,y};
    if(op==1) v[cur].push_back(W1(x,y)),v[cur].push_back(W2(x,y));
    else if(op==2) v[cur].push_back(W1(x,y)),v[cur].push_back(W3(x,y));
    else if(op==3) v[cur].push_back(W3(x,y)),v[cur].push_back(W4(x,y));
    else if(op==4) v[cur].push_back(W2(x,y)),v[cur].push_back(W4(x,y));
}
int main()
{
    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
    {
        mp[(node){0,0}]=1;
        an[1]=(node){1,1},mp[an[1]]=1,ans++;
        mp[W1(an[1].x,an[1].y)]=1;
        if(work(1,m,1))
            an[++ans]=(node){1,m},mp[W2(an[2].x,an[2].y)]=1;
        if(work(n,1,1))
            an[++ans]=(node){n,1},mp[W3(an[3].x,an[3].y)]=1;
        if(work(n,m,1))
            an[++ans]=(node){n,m},mp[W4(an[4].x,an[4].y)]=1;
        for(int i=2,cur=2;i<=n||i<=m;i++)
        {
            int las=cur+1;
            id(1,i,cur,1),id(1,m-i+1,cur,1);
            id(i,1,cur,2),id(n-i+1,1,cur,2);
            id(n,i,cur,3),id(n,m-i+1,cur,3);
            id(i,m,cur,4),id(n-i+1,m,cur,4);
            for(int j=las;j<=cur;j++)
            {
                for(int k=0;k<v[j].size();k++)
                    if(mp[v[j][k]]>=las)
                        du[j]++;
                s.insert(make_pair(du[j],j));
            }
            while(!s.empty())
            {
                int x=(*s.begin()).second;
                s.erase(make_pair(du[x],x));
                if(mp[re[x]]>=las)
                {
                    an[++ans]=re[x],mp[re[x]]=1;
                    for(int k=0;k<v[x].size();k++)
                    {
                        int y=mp[v[x][k]];
                        if(y>=las)
                        {
                            s.erase(make_pair(du[y],y)),du[y]=0;
                            s.insert(make_pair(du[y],y));
                        }
                        mp[v[x][k]]=1;    
                    }
                }
                else
                {
                    for(int k=0;k<v[x].size();k++)
                    if(mp[v[x][k]]>=las)
                    {
                        int y=mp[v[x][k]];
                        s.erase(make_pair(du[y],y)),du[y]--;
                        s.insert(make_pair(du[y],y));
                    }
                }
            }
        }
    }
    prin(ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 29628kb

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: 2ms
memory: 29316kb

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: 399ms
memory: 65660kb

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: 415ms
memory: 64032kb

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: 220ms
memory: 56372kb

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)