抢一个C++最短解(896B)
查看原帖
抢一个C++最短解(896B)
120868
dbxxx楼主2022/12/10 17:00

感觉应该不违规,因为有一个先例?

896B,应该还可以再压,但我累了(

评测记录 https://www.luogu.com.cn/record/96982813

#include<bits/stdc++.h>
using namespace std;
#define B d[x]
#define C z[B]
#define D int
#define E(b)K Z(a[j]):b;
#define F push_back
#define G(a)for(i=1;i<=a;++i)
#define H back()
#define I clear()
#define K for(j=i+1;j<n;++j)a[j]^y?
#define L P(t)
#define M P(B)
D i,j,T,n,m,p,y,v,t,x,a[1<<21],d[605];deque<D>z[305];vector<pair<D,D>>b;vector<D>q;D P(D s,D t=0){b.F({s,t});return 0;}D Z(D x){return B?q.F(B),x^C.H?C.pop_front(),L,P(t,B):(C.pop_back(),M),B=0:q.size()?B=q.H,q.pop_back(),C.F(x),M:1;}main(){for(cin>>T;T--;){cin>>n>>m>>p;G(m)cin>>a[i];fill(d,d+n*2,0);b.I;t=n;q.I;G(n-1)q.F(i),q.F(i);G(m)if(p=a[i],Z(p)){n=i+1;for(x=a[n];x^p&&C.H==x;x=a[++n]);if(x^p){y=C.H;v=1;K 0:v^=1;if(v){M;C.F(p);E(L)L;P(t,B);C.pop_front();d[p]=B;B=0;}else{L;z[t].F(p);E(M)M;C.I;d[p]=t;q.F(t);t=B;B=d[y]=0;}}else{L;E(Z(a[j]))L;}i=n;}printf("%d\n",b.size());for(auto[p,q]:b)printf(q?"2 %d %d\n":"1 %d\n",p,q);}}

还原这份代码的宏定义,去掉三目运算符,且完全不压行后是下面这样的,大小 1.69KB,也已经比绝大部分 AC 记录小了(大部分都是 3K,4K 的)。供参考。(不过最后 printf 的使用挺不规范的。)

#include <bits/stdc++.h>
using namespace std;
#define N 305
#define M 2000005
int a[M];
deque<int>z[N];
int d[N*2];
typedef pair<int,int>pii;
vector<pii>ans;
inline void P(int s,int t=0){
	ans.push_back({s,t});
}
int t;
queue<int>q;
inline bool S(int x){
	int s=d[x];
	if(s){
		d[x]=0;
		q.push(s);
		if(x^z[s].back()){
			P(t);
			P(t,s);
			z[s].pop_front();
		}else{
			P(s);
			z[s].pop_back();
		}
	}else{
		if(q.empty())
			return true;
		d[x]=s=q.front();
		q.pop();
		P(s);
		z[s].push_back(x);
	}
	return false;
}
main(){
	int T;
	for(scanf("%d",&T);T--;){
		int n,m;
		scanf("%d%d%*d",&n,&m);
		for(int i=1;i<=m;++i)
			scanf("%d",&a[i]);
		fill(d,d+n*2,0);
		ans.clear();
		t=n;
		while(q.size())
			q.pop();
		for(int i=1;i<n;++i){
			q.push(i);
			q.push(i);
		}
		for(int i=1;i<=m;++i) if(S(a[i])){
			int p=a[i];
			int r=i+1,x=a[r];
			for(;x^p&&z[d[x]].back()==x;x=a[++r]);
			if(x^p){
				int s=d[x],y=z[s].back(),v=1;
				for(int j=i+1;j<r;++j)
					if(a[j]==y)
						v^=1;
				if(v){
					P(s);
					z[s].push_back(p);
					for(int j=i+1;j<r;++j){
						if(a[j]^y)
							S(a[j]);
						else
							P(t);
					}
					P(t);
					P(t,s);
					z[s].pop_front();
					d[x]=0;
					d[p]=s;
				}else{
					P(t);
					z[t].push_back(p);
					for(int j=i+1;j<r;++j){
						if(a[j]^y)
							S(a[j]);
						else
							P(s);
					}
					P(s);
					z[s].clear();
					d[x]=d[y]=0;
					d[p]=t;
					q.push(t);
					t=s;
				}
			}else{
				P(t);
				for(int j=i+1;j<r;++j)
					S(a[j]);
				P(t);
			}
			i=r;
		}
		printf("%d\n",ans.size());
		for(auto[p,q]:ans)
			printf(q?"2 %d %d\n":"1 %d\n",p,q);
	}
	return 0;
}
2022/12/10 17:00
加载中...