RE求调
- 板块P8866 [NOIP2022] 喵了个喵
- 楼主CharlieCai
- 当前回复0
- 已保存回复0
- 发布时间2024/5/27 13:58
- 上次更新2024/5/27 18:25:39
查看原帖
被骇客银狼阻止的越权访问保存失败
RE求调
#include<bits/stdc++.h>
#define MAXN 4000005
#define N 1005
using namespace std;
int T,n,m,k,op,a[MAXN],cnt,sp;
int t[MAXN],f[MAXN],b[MAXN],d[MAXN];
struct Opt{
int k,x,y;
}opt[MAXN];
deque<int>s[N];
queue<int>q;
void csh(){
cnt=0;
op=0;
memset(opt,0,sizeof(opt));
memset(b,0,sizeof(b));
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
memset(t,0,sizeof(t));
while(!q.empty())q.pop();
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++)q.push(i);
sp=n;
}
void tepan(){
if(n==1){
printf("%d\n",m);
for(int i=1;i<=m;i++){
printf("1 1\n");
}
}
}
void type1(int i){
//cot<<"type:1"<<endl;
int tmp=t[a[i]];
if(!s[tmp].empty())s[tmp].pop_back();
if(s[tmp].size()==1)q.push(tmp);//cot<<"!!!!!qpush"<<tmp<<endl;
if(!s[tmp].size()&&!sp)sp=tmp;
t[a[i]]=0;
if(!s[tmp].size())f[a[i]]=0;
else t[s[tmp].back()]=tmp;
opt[++op]=(Opt){1,tmp,0};
//pritf("1 %d\n",opt[op].x);
}
void type2(int i){
int tmp=f[a[i]];
//cot<<"type:2"<<tmp<<endl;
opt[++op]=(Opt){1,sp,0};
//pritf("1 %d\n",opt[op].x);
opt[++op]=(Opt){2,tmp,sp};
//pritf("2 %d %d\n",opt[op].x,opt[op].y);
if(!s[tmp].empty())s[tmp].pop_front();
if(s[tmp].size()==1)q.push(tmp);//cot<<"!!!!!qpush"<<tmp<<endl;
if(!s[tmp].size()&&!sp)sp=tmp;
f[a[i]]=0;
t[a[i]]=0;
if(s[tmp].size())f[s[tmp].front()]=tmp;
}
void type3(int i){
//cot<<"type:3"<<endl;
if(q.empty())
{
return ;
}
int tmp=q.front();
//cot<<"qsize"<<q.size()<<" tmp:"<<tmp<<endl;
s[tmp].push_back(a[i]);
t[a[i]]=tmp;
if(s[tmp].size()==1)f[a[i]]=tmp;
else t[s[tmp].front()]=0;
d[a[i]]=tmp;
if(s[tmp].size()==2){
if(!q.empty())
q.pop();
//cot<<"!!!!!qpop"<<tmp<<endl;
}
opt[++op]=(Opt){1,tmp,0};
if(!b[a[i]])cnt++;
b[a[i]]++;
//cot<<"++bai\n";
//pritf("1 %d\n",opt[op].x);
}
void type40(int j,int dtmp){
//cot<<"type:4:0\n"<<j<<"\n";
opt[++op]=((Opt){1,dtmp,0});
b[a[j]]--;
d[a[j]]=0;
if(!b[a[j]])cnt--;
//cot<<"--baj"<<a[j]<<"\n";
t[a[j]]=0;
if(!s[dtmp].empty()){
t[s[dtmp].back()]=dtmp;
//cot<<"bu dtmp"<<s[dtmp].back()<<' '<<dtmp<<endl;
}else{
f[a[j]]=0;
}
//pritf("1 %d\n",opt[op].x);
//cot<<"xiao"<<a[j]<<endl;
}
void add(int j){
if(b[a[j]]){
if(t[a[j]]){
int tmpp=t[a[j]];
if(!s[tmpp].empty())s[tmpp].pop_back();
if(s[tmpp].size()==1)q.push(tmpp);//cot<<"!!!!!qpush"<<tmpp<<endl;
if(!s[tmpp].size()&&!sp)sp=tmpp;
t[a[j]]=0;
opt[++op]=(Opt){1,tmpp,0};
d[a[j]]=0;
b[a[j]]--;
if(!b[a[j]])cnt--;//cot<<"--cnt\n";
//cot<<"--baj"<<a[j]<<"\n";
//pritf("1 %d\n",opt[op].x);
if(!s[tmpp].empty())t[s[tmpp].back()]=tmpp;
else f[a[j]]=0;
}else{
s[d[a[j]]].push_back(a[j]);
if(s[d[a[j]]].size()>1)t[s[d[a[j]]].front()]=0;
t[a[j]]=d[a[j]];
if(!b[a[j]])cnt++;//cot<<"++cnt\n";
b[a[j]]++;
//cot<<"++baj"<<a[j]<<"\n";
opt[++op]=(Opt){1,d[a[j]],0};
//pritf("1 %d\n",opt[op].x);
}
}else{
//cot<<"type:4:3\n";
if(q.empty())return ;
int tmpp=q.front();
s[tmpp].push_back(a[j]);
t[a[j]]=tmpp;
if(s[tmpp].size()==1)f[a[j]]=tmpp;
else if(s[tmpp].size()==2) t[s[tmpp].front()]=0;
d[a[j]]=tmpp;
if(s[tmpp].size()==2)
{
if(!q.empty())q.pop();
}//cot<<"!!!!!qpop"<<tmpp<<endl;
opt[++op]=(Opt){1,tmpp,0};
if(!b[a[j]])cnt++;//cot<<"++cnt\n";
b[a[j]]++;
//cot<<"++baj"<<a[j]<<"\n";
//cot<<"err";
//pritf("1 %d\n",opt[op].x);
}
}
void output(){
printf("%d\n",op);
for(int i=1;i<=op;i++){
if(opt[i].k==1){
printf("1 %d\n",opt[i].x);
}else{
printf("2 %d %d\n",opt[i].x,opt[i].y);
}
}
}
signed main(){
//freopen("meow2.in","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
while(T--){
csh();
if(n==1){
tepan();
continue;
}
for(int i=1;i<=m;i++){
//cot<<'I'<<i<<' '<<a[i]<<' '<<b[a[i]]<<endl;
//cot<<"CNT:"<<cnt<<endl;
//cot<<"SP:"<<sp<<endl;
if(b[a[i]]){
if(t[a[i]]){
type1(i);
}else{
type2(i);
}
d[a[i]]=0;
b[a[i]]--;
//cot<<"--bai\n";
if(!b[a[i]])cnt--;
}else{
if(cnt<2*n-2){
type3(i);
}else{
//cot<<"type:4"<<endl;
//cot<<"sbCNT:"<<cnt<<endl;
int tmp,cntt=0,tmpj;
for(int j=i+1;j<=m;j++){
if((!t[a[j]])||(a[j]==a[i])){
//cot<<"a[j]"<<a[j]<<' '<<"f[a[j]]"<<f[a[j]]<<endl;
tmp=a[j];
tmpj=j;
break;
}
}
int dtmp=d[tmp];
int sb=s[dtmp].back();
if(tmp==a[i]){
opt[++op]=(Opt){1,sp,0};
if(!b[a[i]])cnt++;
//cot<<"++bai\n";
b[a[i]]++;
d[a[i]]=sp;
//pritf("1 %d\n",opt[op].x);
for(int j=i+1;j<tmp;j++){
add(j);
}
opt[++op]=(Opt){1,sp,0};
//pritf("1 %d\n",opt[op].x);
if(!b[a[i]])cnt--;
d[a[i]]=0;
b[a[i]]--;
}
else{
for(int j=i+1;j<tmpj;j++){
if(s[dtmp].empty()||a[j]==s[d[tmp]].back())cntt++;
}
//cot<<cntt<<endl;
//pritf("tmp:%d tmpj:%d cntt:%d t:%d\n",tmp,tmpj,cntt,s[d[tmp]].back());
if(cntt%2==1){
int tsp=f[tmp];
//cot<<"hzs AK IOI!!!\n"<<endl;
s[sp].push_back(a[i]);
d[a[i]]=t[a[i]]=f[a[i]]=sp;
if(!b[a[i]])cnt++;
b[a[i]]++;
//cot<<"++baj\n";
opt[++op]=(Opt){1,sp,0};
//pritf("1 %d\n",opt[op].x);
// sp=0;
for(int j=i+1;j<tmpj;j++){
//cot<<"JJJ:"<<j<<"\n";
if(a[j]==sb){
type40(j,dtmp);
}else{
add(j);
}
}
opt[++op]=((Opt){1,dtmp,0});
//pritf("1 %d\n",opt[op].x);
s[dtmp].clear();
d[a[i]]=t[a[i]]=f[a[i]]=sp;
q.push(sp);
//cot<<"!!!!!qpush"<<sp<<endl;
sp=tsp;
b[tmp]--;
//cot<<"--bsb"<<tmp<<"\n";
d[tmp]=t[tmp]=f[tmp]=0;
b[a[tmpj]]=d[a[tmpj]]=t[a[tmpj]]=f[a[tmpj]]=0;
if(!b[a[tmp]])cnt--;
}else{
if(s[d[tmp]].size()>1)t[s[d[tmp]].back()]=0,//cot<<"Hzs AK IOI!!!!!!!!!!!!!"<<s[d[tmp]].back()<<endl;
s[d[tmp]].push_back(a[i]);
t[a[i]]=d[tmp];
if(!b[a[i]])cnt++;
b[a[i]]++;
opt[++op]=(Opt){1,d[tmp],0};
//pritf("1 %d\n",opt[op].x);
for(int j=i+1;j<tmpj;j++){
add(j);
}
opt[++op]=(Opt){1,sp,0};
//pritf("1 %d\n",opt[op].x);
opt[++op]=(Opt){2,d[tmp],sp};
//pritf("2 %d %d\n",opt[op].x,opt[op].y);
if(!s[d[tmp]].empty())s[d[tmp]].pop_front();
if(s[d[tmp]].size())f[s[d[tmp]].front()]=d[tmp];
b[tmp]--;
if(!b[tmp])cnt--;//cot<<"--cnt\n";
//cot<<"--btmp"<<tmp<<"\n";
d[tmp]=0;
}
}
i=tmpj;
}
}
}
output();
}
return 0;
}
/*
4 28 7
1 2 3 4 5 6 7 6 5 6 5 4 2 4 2 1 1 5 4 6 5 4 7 1 2 3 5 4
*/
加载中...