AtCoder taught me a lesson

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.