QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199458 | #7178. Bishops | kiwiHM# | WA | 415ms | 65660kb | C++14 | 4.0kb | 2023-10-04 12:25:16 | 2023-10-04 12:25:17 |
Judging History
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)