Abstract
Never use reference value on std::priority_queue
, otherwise it will be affected when you push in something "greater" than it. I lose my first chance to AK an ABC in this reason.
Detail
When I was solving D, I wrote this
while(q.size()){
auto& [stp,t1,t2]=q.top();
q.pop();
auto& [drx1,dry1]=t1;
auto& [drx2,dry2]=t2;
if(t1==t2){
printf("%d\n",stp);
exit(0);
}
for(int i=0;i<n;i++){
int nx1=drx1+dx[i],nx2=drx2+dx[i],
ny1=dry1+dy[i],ny2=dry2+dy[i];
if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
if(vis[nx1][ny1][nx2][ny2])continue;
vis[nx1][ny1][nx2][ny2]=true;
q.push({stp+1,{nx1,ny1},{nx2,ny2}});
}
}
It seems no flaw in it, but when I input
5
....#
#..#.
.P...
..P..
....#
it threw segmentation fault.
Then, I add some debug code
...
printf("%d %d %d %d\n",drx1,dry1,drx2,dry2);
fflush(stdout);
...
printf("%d\n",i);
fflush(stdout);
...
printf("%d %d %d %d\n",nx1,ny1,nx2,ny2);
fflush(stdout);
in it, and it put
2 1 3 2
0
2 2 3 3
1
3 2 4 3
2
-14220976 545 -15256416 545
before it ran into the segmentation fault.
I realized that the container did something like cumulative sum. It's not what I want.
Then, I deleted all the character &
in my code and modified it to
while(q.size()){
auto [stp,t1,t2]=q.top();
q.pop();
auto [drx1,dry1]=t1;
auto [drx2,dry2]=t2;
if(t1==t2){
printf("%d\n",stp);
exit(0);
}
for(int i=0;i<4;i++){
int nx1=drx1+dx[i],nx2=drx2+dx[i],
ny1=dry1+dy[i],ny2=dry2+dy[i];
fflush(stdout);
if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
printf("%d %d %d %d %d\n",stp,nx1,ny1,nx2,ny2);
if(vis[nx1][ny1][nx2][ny2])continue;
vis[nx1][ny1][nx2][ny2]=true;
q.push({stp+1,{nx1,ny1},{nx2,ny2}});
}
}
and it put
0 2 2 3 3
0 3 1 4 2
0 2 0 3 1
0 1 1 2 2
1 3 2 4 3
1 4 1 4 2
1 3 0 4 1
1 2 1 3 2
2 4 2 4 3
2 4 1 4 2
2 4 0 4 1
2 3 1 3 2
3 4 3 4 3
3 4 2 4 3
3 4 1 4 2
3 3 2 3 3
4
it's the wrong answer.
I spend about 5 minutes to realize that priority_queue
put the greatest element at the top, then I modified it a bit to
while(q.size()){
auto [stp,t1,t2]=q.top();
q.pop();
auto [drx1,dry1]=t1;
auto [drx2,dry2]=t2;
if(t1==t2){
printf("%d\n",-stp);
exit(0);
}
for(int i=0;i<4;i++){
int nx1=drx1+dx[i],nx2=drx2+dx[i],
ny1=dry1+dy[i],ny2=dry2+dy[i];
// fflush(stdout);
if(max(nx1,ny1)>=n or min(nx1,ny1)<0 or s[nx1][ny1]=='#')nx1-=dx[i],ny1-=dy[i];
if(max(nx2,ny2)>=n or min(nx2,ny2)<0 or s[nx2][ny2]=='#')nx2-=dx[i],ny2-=dy[i];
// printf("%d %d %d %d %d\n",stp+1,nx1,ny1,nx2,ny2);
if(vis[nx1][ny1][nx2][ny2])continue;
vis[nx1][ny1][nx2][ny2]=true;
q.push({stp-1,{nx1,ny1},{nx2,ny2}});
}
}
then it finally put the correct answer.
Thanks atcoder_official for your lesson, and the easiest G ever that's also the first G I solved during the contest.