80分求调QAQ
查看原帖
80分求调QAQ
602361
114514wxy楼主2023/8/4 09:49

#8#9TLE 合并不会做就用判断跳过了 但是感觉理论上复杂度O(n)啊 自己跑了跑到六秒钟QAQ(跑的第八个点)

#include<bits/stdc++.h>
using namespace std;
const int N=200003;

int n,tot=1;
bool kinds[N];
struct blocks{
	int l,r;
	int nxt,prev;
	bool kin;
} a[N];

inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void pr(int x){
	if(x>9) pr(x/10);
	putchar(x%10+'0');
}

int main(){
	//freopen("P7912_8.in","r",stdin);
	//freopen("o.out","w",stdout);
	n=read(),kinds[1]=read();
	a[tot].kin=kinds[1];
	if(a[1].kin==0)a[0].kin=1;a[0].nxt=1;
	a[tot].l=1;
	for(int i=2;i<=n;++i){
		kinds[i]=read();
		if(kinds[i]!=a[tot].kin){
			a[tot].r=i-1;
			a[tot].nxt=tot+1;
			a[++tot].l=i;
			a[tot].prev=tot-1;
			a[tot].kin=kinds[i];
		}
	}
	a[tot].nxt=tot+1,a[tot].r=n;
	a[tot+1].nxt=-1;
	
	while(a[0].nxt<=tot){
		
		bool chang=!a[a[0].nxt].kin;
		for(int i=a[0].nxt;i>0;i=a[i].nxt){
			if(a[i].nxt==-1) break;
			if(chang==a[i].kin)	continue;
			
			pr(a[i].l);
			putchar(0);
			
			++a[i].l;
			chang=a[i].kin;
			if(a[i].l>a[i].r){
				a[a[i].nxt].prev=a[i].prev;
				a[a[i].prev].nxt=a[i].nxt;
			}
		}printf("\n");//for(int i=0;i>=0;i=a[i].nxt) printf("a[%d].prev=%d,.nxt=%d,.l=%d,.r=%d,.kin=%d\n",i,a[i].prev,a[i].nxt,a[i].l,a[i].r,a[i].kin);
	}
	return 0;
}
2023/8/4 09:49
加载中...