c++ - 最小数のスワップを使用して 2 つの行を一緒に並べ替える

Question

SPOJの質問:

私のアルゴリズムは、1 から N まで反復することです。各反復で、2 つの「i」が入っているボックスを見つけます。たとえば、最初の反復でのこのデータムの場合:

3 3

2 2

1 1

両方の1の位置を保存します。次に、元の位置に近い特定の i を、その前のボックス内の 2 つのボールのうち大きい方のボールと交換して移動を開始します。その前のボックスに同じボールが含まれている場合、ボール「i」を反対側の列のボールと交換します。したがって、上記の場合、最初の繰り返しで、最初の列の 1 を 2 番目の列の 2 と交換します。最初のボール i がその位置に到達したら、もう一方のボール i についても同じことを行います。アルゴリズムは次のようになります。

#include <iostream>
using namespace std;

static int mark[2][9], in[2][9];
int N, ANS=0, s1, s2, r, t1, t2, v1, v2, p, tmp;

int main(){
    cin >> N;
    for(int i=1; i<=N; ++i)cin >> in[0][i] >> in[1][i];  //Inputting 

    for(int i=1; i<=N; ++i){
        for(int j=1; j<=N; ++j){                         //Searching for one of the i.
            if(in[0][j]==i){s1=j; v1=0; break;}
            if(in[1][j]==i){s1=j; v1=1; break;}
        }
        in[v1][s1]=1234;                                 //temporarily removing the i found. 
        for(int j=1; j<=N; ++j){                         //finding the other i
            if(in[1][j]==i){s2=j; v2=1; break;}
            if(in[0][j]==i){s2=j; v2=0; break;}
        }
        in[v1][s1]=i;                                          //restoring previous i

        if(s1==s2){                                            //Deciding on which i to begin swapping with.
            int m=s1, chk;
            while(m>0 && in[0][m]==in[1][m])m--;
            chk=(s1+m)%2; t1=t2=s1;
            if(chk && in[!v1][m]<in[!v2][m]){r=v2; v2=v1; v1=r;}
            else if(!chk && in[v1][m]<in[v2][m]){r=v2; v2=v1; v1=r;}
        }
        else{
            if(s1>s2){r=v2; v2=v1; v1=r;}
            t1=(s1<s2)?s1:s2; t2=(s1<s2)? s2:s1;
        }

        r=v1;
        while(t1>i){                                          //moving the first i to required position.
            if(in[0][t1-1]>in[1][t1-1])p=0;
            else if(in[0][t1-1]<in[1][t1-1])p=1;            //Deciding on the balls to swap.
            else p=!r;

            tmp=in[p][t1-1]; in[p][t1-1]=in[r][t1]; in[r][t1]=tmp; //Swapping
            r=p; t1-=1; 
            ANS+=1;                                      //incrementing swaps.
        }

        r=v2;                                            //Doing the same for the second i.
        while(t2>i){                         
            if(in[0][t2-1]>in[1][t2-1])p=0;
            else if(in[0][t2-1]<in[1][t2-1])p=1;
            else p=!r;
            tmp=in[p][t2-1]; in[p][t2-1]=in[r][t2]; in[r][t2]=tmp;
            r=p; t2-=1; ANS+=1;
        }
    }
    cout << ANS << '\n';          //Printing the answer.
    return 0;
}

私はこれに対して間違った答えを得ていますが、私のコードはサンプル テスト ケースとカスタム テスト ケースで機能します。プログラムが失敗したり、アルゴリズムのエラーを指摘したりするテストケースをいくつか指摘できますか。

ありがとうございました。