记录编号	581796	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3812.[NOIP 2022] 喵了个喵	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	5.826 s
提交时间	2023-08-13 19:42:38	内存使用	11.02 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 310,M = 2e6+10;
int T,n,m,k;
int a[M],id[2*N];//a为原数组 id为某类牌所在栈编号,没有则为0 
struct made{
	int v1,v2;
}; 
int stp;//辅助栈编号 
deque<int>st[N];//每个栈 
queue<int>q;//维护空栈 
vector<made>ans;//答案 
void first_() {
	ans.clear();//清空答案 
	stp = n;//最开始辅助栈定为n 
	memset(id,0,sizeof(id));
}
void pu(int x,int y){
	ans.push_back((made){x,y});
}
bool simple(int x){
	int stx = id[x];
	if(!stx){
		if(q.empty())return false;
		id[x] = stx = q.front();
		q.pop();
		pu(stx,0);
		st[stx].push_back(x);
	}
	else{
		id[x] = 0;
		q.push(stx);
		if(st[stx].back() == x){
			pu(stx,0);
			st[stx].pop_back();
		}
		else{
			pu(stp,0);//首先放到辅助栈里
			pu(stx,stp);
			st[stx].pop_front();
		}
	}
	return true;
}
int main(){
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);//n个栈 m个卡牌 k种卡牌 
		first_();
		for(int i = 1;i <= m;i++) 
			scanf("%d",&a[i]);//离线操作
		while(!q.empty())q.pop();
		for(int i = 1;i < n;i++){q.push(i);q.push(i);}
		for(int i = 1;i <= m;i++){
			if(!simple(a[i])){
				int now = a[i],nx = i+1;int x = a[nx];
				for(;nx <= m && x != now && x == st[id[x]].back();nx++,x = a[nx]);
				//此时 nx 是 i 后第一个不在栈顶上的下标，x 是 a[nx]
				if(x == now){
					pu(stp,0);
					for(int j = i+1;j < nx;j++)simple(a[j]);
					pu(stp,0);
				}
				else{
					int stx = id[x];int y = st[stx].back();
					bool flag = true;//判断奇偶数 
					for(int j = i+1;j < nx;j++)
					    if(a[j] == y)flag = !flag;
					if(flag){//偶数 
						pu(stx,0);
						st[stx].push_back(a[i]);
						for(int j = i+1;j < nx;j++){
							if(a[j] == y)pu(stp,0);
							else simple(a[j]);
						}
						pu(stp,0);pu(stx,stp);
						st[stx].pop_front();
						id[x] = 0;id[now] = stx;
					}
					else{//奇数 
						pu(stp,0);
						st[stp].push_back(now);
						for(int j = i+1;j < nx;j++){
							if(a[j] == y)pu(stx,0);
							else simple(a[j]);
						}
						pu(stx,0);
						st[stx].clear();
						//清空当前栈 
						id[x] = id[y] = 0;
						id[now] = stp;
						q.push(stp);
						stp = stx;
					}
				}
				i = nx;//因为循环内i会自动++,所以只需要赋值为r,自动r+1 
			} 
		}
		printf("%d\n",ans.size());
		for(int i = 0;i < ans.size();i++){
			if(ans[i].v2)printf("2 %d %d\n",ans[i].v1,ans[i].v2);
			else printf("1 %d\n",ans[i].v1);
		}
	}
	
	
	return 0;
	
}