提交记录

代码：

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
#define debug cout<<"FUCKCCF!"<<endl;
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
const int N=2e6+10;
int T,n,m,k,a[N],cnt,spe,belong[N];
struct node{int op,x,y;}ans[N<<2];
vector<deque<int> > s(610);
queue<int> q;
void opera1(int x,int t){
	ans[++cnt]={1,x};
	if(s[x].size()>0&&s[x].back()==t){
		s[x].pop_back();
		if(x!=spe&&s[x].size()<2) q.push(x);
		belong[t]=0;
	}
	else{
		s[x].push_back(t);
		belong[t]=x;
	}
}
void opera2(int x,int y){
	ans[++cnt]={2,x,y};
	belong[s[x].front()]=0;
	s[x].pop_front(),s[y].pop_front();
	if(s[x].size()<2) q.push(x);
}
void init(){
	while(!q.empty()) q.pop();
	cnt=0;s.clear();
	FOR(i,0,k) belong[i]=0;
}
int main(){
	
	//freopen("meow2.in","r",stdin);
	//freopen("meow.out","w",stdout);
	T=rd;
	while(T--){
		init();n=rd,m=rd,k=rd;
		FOR(i,1,m) a[i]=rd;
		FOR(i,1,n-1) q.push(i),q.push(i);
		spe=n;
		FOR(i,1,m){
			int x=belong[a[i]];
			if(x){
				if(s[x].size()==1) opera1(x,a[i]);
				else if(s[x].back()==a[i]) opera1(x,a[i]);
				else opera1(spe,a[i]),opera2(x,spe);
			}
			else if(q.size()>0){
				x=q.front();q.pop();
				opera1(x,a[i]);
			}
			else{
				for(int j=i+1;;j++){
					if(a[j]==a[i]) break;
					if(s[belong[a[j]]][0]==a[j]){x=belong[a[j]];break;}
				}
				if(!x) opera1(spe,a[i]);
				else{
					int u=s[x].front(),v=s[x].back();
					for(int j=i+1;;j++){
						if(a[j]==u){
							opera1(x,a[i]);
							break;
						}
						else if(a[j]==v){
							opera1(spe,a[i]),q.push(spe),spe=x;
							break;
						}
					}
				} 
			}
		}
		printf("%d\n",cnt);
		FOR(i,1,cnt){
			if(ans[i].op==1) printf("%d %d\n",ans[i].op,ans[i].x);
			else printf("%d %d %d\n",ans[i].op,ans[i].x,ans[i].y);
		}
	}
	return 0;
}