RT，求调，又长又丑

提交记录

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e6+84;
const int maxn=384;
int T,n,m,k,j,f,cnt,anscnt,c[maxm],adr[maxn*2];
queue<int> q;
deque<int> dq[maxn];//双端队列
pair<int,int> ans[maxm*2];
int main(){
    scanf("%d",&T);
    while(T--){
        memset(adr,0,sizeof(adr));
        while(!q.empty())
            q.pop();
        anscnt=0;
        scanf("%d%d%d",&n,&m,&k);
        f=n;
        for(int i=1;i<=m;i++)
            scanf("%d",&c[i]);
        for(int i=1;i<n;i++)
            q.push(i),q.push(i);
        for(int i=1;i<=m;i++){
            if(adr[c[i]]==0&&q.empty()){
                j=i+1;
                while(j<=m&&c[j]!=c[i]&&dq[adr[c[j]]].front()==c[j])
                    j++;
                if(c[i]==c[j]){
                    ans[++anscnt]={24202,f};
                    for(k=i+1;k<j;k++){
                        if(!adr[c[k]]){
                            adr[c[k]]=q.front();
                            q.pop();
                            dq[adr[c[k]]].push_front(c[k]);
                            ans[++anscnt]={24202,adr[c[k]]};
                        }
                        else{
                            if(dq[adr[c[k]]].front()==c[k]){
                                dq[adr[c[k]]].pop_front();
                                ans[++anscnt]={24202,adr[c[k]]};
                            }
                            else{
                                dq[adr[c[k]]].pop_back();
                                ans[++anscnt]={24202,f};
                                ans[++anscnt]={adr[c[k]],f};
                            }
                            q.push(adr[c[k]]);
                            adr[c[k]]=0;
                        }
                    }
                    ans[++anscnt]={24202,f};
                }
                else{
                    cnt=0;
                    for(k=i+1;k<j;k++)
                        if(c[k]==dq[adr[c[j]]].front())
                            cnt++;
                    if(cnt&1){
                        ans[++anscnt]={24202,f};
                        dq[f].push_front(c[i]);
                        adr[c[i]]=f;
                        for(k=i+1;k<j;k++){
                            if(c[k]==dq[adr[c[j]]].front())
                                ans[++anscnt]={24202,adr[c[j]]};
                            else{
                                if(!adr[c[k]]){
                                    adr[c[k]]=q.front();
                                    q.pop();
                                    dq[adr[c[k]]].push_front(c[k]);
                                    ans[++anscnt]={24202,adr[c[k]]};
                                }
                                else{
                                    if(dq[adr[c[k]]].front()==c[k]){
                                        dq[adr[c[k]]].pop_front();
                                        ans[++anscnt]={24202,adr[c[k]]};
                                    }
                                    else{
                                        dq[adr[c[k]]].pop_back();
                                        ans[++anscnt]={24202,f};
                                        ans[++anscnt]={adr[c[k]],f};
                                    }
                                    q.push(adr[c[k]]);
                                    adr[c[k]]=0;
                                }
                            }
                        }
                        ans[++anscnt]={24202,adr[c[j]]};
                        q.push(f);
                        f=adr[c[j]];
                        adr[c[j]]=adr[dq[adr[c[j]]].front()]=0;
                        dq[adr[c[j]]].clear();
                    }
                    else{
                        ans[++anscnt]={24202,adr[c[j]]};
                        dq[adr[c[j]]].push_front(c[i]);
                        for(k=i+1;k<j;k++){
                            if(c[k]==dq[adr[c[j]]].front())
                                ans[++anscnt]={24202,f};
                            else{
                                if(!adr[c[k]]){
                                    adr[c[k]]=q.front();
                                    q.pop();
                                    dq[adr[c[k]]].push_front(c[k]);
                                    ans[++anscnt]={24202,adr[c[k]]};
                                }
                                else{
                                    if(dq[adr[c[k]]].front()==c[k]){
                                        dq[adr[c[k]]].pop_front();
                                        ans[++anscnt]={24202,adr[c[k]]};
                                    }
                                    else{
                                        dq[adr[c[k]]].pop_back();
                                        ans[++anscnt]={24202,f};
                                        ans[++anscnt]={adr[c[k]],f};
                                    }
                                    q.push(adr[c[k]]);
                                    adr[c[k]]=0;
                                }
                            }
                        }
                        ans[++anscnt]={24202,f};
                        ans[++anscnt]={adr[c[j]],f};
                        dq[adr[c[j]]].pop_back();
                        adr[c[i]]=adr[c[j]];
                        adr[c[j]]=0;
                    }
                }
                i=j;
            }
            else{
                if(!adr[c[i]]){
                    adr[c[i]]=q.front();
                    q.pop();
                    dq[adr[c[i]]].push_front(c[i]);
                    ans[++anscnt]={24202,adr[c[i]]};
                }
                else{
                    if(dq[adr[c[i]]].front()==c[i]){
                        dq[adr[c[i]]].pop_front();
                        ans[++anscnt]={24202,adr[c[i]]};
                    }
                    else{
                        dq[adr[c[i]]].pop_back();
                        ans[++anscnt]={24202,f};
                        ans[++anscnt]={adr[c[i]],f};
                    }
                    q.push(adr[c[i]]);
                    adr[c[i]]=0;
                }
            }
            // printf("%d %d %d %d %d %d\n",f,i,adr[1],adr[2],adr[3],c[i+1]);
        }
        printf("%d\n",anscnt);
        for(int i=1;i<=anscnt;i++)
            if(ans[i].first==24202)
                printf("1 %d\n",ans[i].second);
            else
                printf("2 %d %d\n",ans[i].first,ans[i].second);
    }
    return 0;
}