Submission #34047518

---

Source Code Expand

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=300005;
int T,n,a[N],pre[N],nex[N],sum[N],ss[N],tt[N];
vector<int>v[5];
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(T);
	rep(tc,1,T){
		rd(n);
		rep(i,0,n-1){
			rd(a[i]);
		}
		bool ok=1;
		rep(_,0,1){
			if(_==1){
				rep(i,0,n-1)a[i]=5-a[i];
			}
			sum[n]=0;
			ss[n]=0;
			tt[n]=0;
			per(i,n-1,0){
				sum[i]=a[i]==2;
				sum[i]+=sum[i+1];
				ss[i]=a[i]==1;
				ss[i]+=ss[i+1];
				tt[i]=a[i]==3;
				tt[i]+=tt[i+1];
			}
			auto get_sum=[&](int *sum,int l,int r){
				if(l<=r){
					return sum[l]-sum[r+1];
				}else{
					return sum[l]+sum[0]-sum[r+1];
				}
			};
			rep(i,1,4)v[i].clear();
			rep(i,0,n-1){
				v[a[i]].pb(i);
			}
			int last=-1;
			rep(i,0,n-1){
				if(a[i]==3)last=i;
			}
			rep(i,0,n-1){
				pre[i]=last;
				if(a[i]==3)last=i;
			}
			per(i,n-1,0){
				if(a[i]==3)last=i;
			}
			per(i,n-1,0){
				nex[i]=last;
				if(a[i]==3)last=i;
			}
			auto get_len=[&](int l,int r){
				if(l<=r)return r-l-1;
				return n-r-1+l;
			};
			auto test=[&](int l,int r){
				if(l==r)return;
				if(get_len(l,r)&&get_sum(ss,l,r)==get_len(l,r)&&get_sum(sum,nex[r],pre[l])==0){
					ok=0;
				}
			};
			auto work=[&](int x){
				if(get_sum(tt,nex[x],pre[x])==tt[0]){
					if(get_len(pre[x],x)&&get_sum(ss,pre[x],x)==get_len(pre[x],x)){
						ok=0;
					}
					if(get_len(x,nex[x])&&get_sum(ss,x,nex[x])==get_len(x,nex[x])){
						ok=0;
					}
				}
				
			};
			rep(i,0,SZ(v[4])-1){
				test(v[4][i],v[4][(i+1)%SZ(v[4])]);
			}
			rep(i,0,SZ(v[4])-1){
				work(v[4][i]);
			}
		}
		puts(ok?"Yes":"No");
	}
	return 0;
}

Submission Info

Judge Result