QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355242#7740. Puzzle: Question MarkNahidameowAC ✓180ms20080kbC++2018.3kb2024-03-16 14:49:482024-03-16 14:49:49

Judging History

你现在查看的是最新测评结果

  • [2024-03-16 14:49:49]
  • 评测
  • 测评结果：AC
  • 用时：180ms
  • 内存：20080kb
查看
  • [2024-03-16 14:49:48]
  • 提交

answer

#include<bits/stdc++.h>
//=========================================================
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
#define pd push_back
#define all(x) x.begin(),x.end()
#define allA(x,l,r) x+l,x+r+1
#define mpr std::make_pair
#define ve std::vector
#define mpre(v) v.insert(v.begin(),0)
#define lb lower_bound
//=========================================================
namespace Balance_tree{
	struct Mes{
		Mes(){}
		friend Mes operator + (Mes A,Mes B){
			Mes ans;
			return ans;
		}
	};
	const int N=2e5+10;
	std::mt19937 rnd(time(NULL));
	struct Mes_BLT{
		struct node{int l,r;ll val;int key,sz;Mes rv,v;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;
			if(tr[rt].l&&tr[rt].r)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v+tr[tr[rt].r].rv;
			else if(tr[rt].l)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v;
			else if(tr[rt].r)tr[rt].rv=tr[rt].v+tr[tr[rt].r].v;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,ll val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(int val,Mes P){int id=newid();return tr[id]={0,0,val,int(rnd()),1,P,P},id;}
		void insert(ll val,Mes P){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val,P)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}Mes query(ll l,ll r){
			int x,y,z;split(rot,r,x,z);
			split(x,l-1,x,y);
			Mes ans=tr[y].rv;
			rot=merge(merge(x,y),z);
			return ans;
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0,Mes(),Mes()};cnt=rot=0;bin.clear();}
	};
	struct Basic_BLT{
		struct node{int l,r;ll val;int key,sz;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,int val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(ll val){int id=newid();return tr[id]={0,0,val,int(rnd()),1},id;}
		void insert(ll val){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}int Get_rank(int rt,int k){
			if(k<=tr[tr[rt].l].sz)return Get_rank(tr[rt].l,k);
			if(k==tr[tr[rt].l].sz+1)return rt;
			return Get_rank(tr[rt].r,k-tr[tr[rt].l].sz-1);
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0};cnt=rot=0;bin.clear();}
	};
}
namespace segment_tree{
	const int N=2e5+10;
	template<typename M,typename T> struct sg_tree{
		struct node{M Mes;T Tag;int l,r;}tr[5];
		int rot;int cnt;
		void init(){for(int i=1;i<=cnt;i++)tr[i].Mes=M(),tr[i].Tag=T(),tr[i].l=tr[i].r=0;rot=cnt=0;}
		void pushup(int rt){
			tr[rt].Mes=M();
			if(tr[rt].l&&tr[rt].r)tr[rt].Mes=tr[tr[rt].l].Mes+tr[tr[rt].r].Mes;
			else if(tr[rt].l)tr[rt].Mes=tr[tr[rt].l].Mes;
			else if(tr[rt].r)tr[rt].Mes=tr[tr[rt].r].Mes;
		}
		void addson(int rt,T x){tr[rt].Mes=tr[rt].Mes+x;tr[rt].Tag=tr[rt].Tag+x;}
		void pushdown(int rt){
			if(tr[rt].Tag==T())return;
			if(tr[rt].l)addson(tr[rt].l,tr[rt].Tag);
			if(tr[rt].r)addson(tr[rt].r,tr[rt].Tag);
			tr[rt].Tag=T();
		}
		void build(int &rt,int l,int r,std::vector<M> &A){
			if(!rt)rt=++cnt;
			if(l==r)return tr[rt].Mes=A[l],void();
			auto mid=l+r>>1;
			build(tr[rt].l,l,mid,A);build(tr[rt].r,mid+1,r,A);
			pushup(rt);
		}
		void change_Seq(int &rt,int l,int r,int x,int y,T P){
			if(x>y)return;
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(x<=l&&r<=y)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid)change_Seq(tr[rt].l,l,mid,x,y,P);
			if(y>mid)change_Seq(tr[rt].r,mid+1,r,x,y,P);
			pushup(rt);
		}
		void change_p(int &rt,int l,int r,int x,T P){
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(l==r)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			(x<=mid)?change_p(tr[rt].l,l,mid,x,P):change_p(tr[rt].r,mid+1,r,x,P);
			pushup(rt);
		}
		M query(int rt,int l,int r,int x,int y){
			if(!rt||x>y)return M();
			if(x<=l&&r<=y)return tr[rt].Mes;
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid&&y>mid)return query(tr[rt].l,l,mid,x,y)+query(tr[rt].r,mid+1,r,x,y);
			if(x<=mid)return query(tr[rt].l,l,mid,x,y);
			if(y>mid)return query(tr[rt].r,mid+1,r,x,y);
			assert(false);
		}
		void build(int l,int r,std::vector<M> &A){build(rot,l,r,A);}
		void change_Seq(int l,int r,int x,int y,T P){
			change_Seq(rot,l,r,x,y,P);}
		void change_p(int l,int r,int x,T P){
			change_p(rot,l,r,x,P);}
		M query(int l,int r,int x,int y){
			return query(rot,l,r,x,y);}
	};
	struct Mes{
		Mes(){}
		Mes(ll _S,int _l,int _r){}
		Mes operator + (Mes P){
			Mes ans=Mes();
			return ans;
		}
	};
	struct Tag{
		Tag(){}
		Tag operator + (Tag P){
			Tag ans=Tag();
			return ans;
		}
		bool operator == (Tag P){return true!=false;}
	};
	Mes operator + (Mes A,Tag B){return A;}
}
namespace Fenwick_Tree{
	const int N=2e5+10;
	struct FwT{
		ll tr[5];int u;
		void init(int _u){
			u=_u;
			for(int i=0;i<=u;i++)tr[i]=0;}
		void add(int x,ll y){for(;x<=u;x+=(x&-x))tr[x]+=y;}
		ll query(int x){ll ans=0;for(;x;x^=(x&-x))ans+=tr[x];return ans;}
		ll query(int l,int r){if(l>r)return 0;return query(r)-query(l-1);}
	};
}
//=========================================================
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll QA(ll x,ll y,ll mod){ll ans=0;for(;y;y>>=1,x=(x<<1)%mod)if(y&1)ans=(ans+x)%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
typedef unsigned U;
const int M=998244353;
struct ModInt{
	static constexpr U mod=M;
	U val;
	constexpr ModInt():val(0U){}
	constexpr ModInt(U _val):val(_val){}
	constexpr ModInt(int _val):val((_val%int(mod)+int(mod))%int(mod)){}
	constexpr ModInt(ll _val):val((_val%ll(mod)+ll(mod))%ll(mod)){}
	ModInt(const ModInt &P):val(P.val){}
	inline ModInt operator +(ModInt p){return ModInt(int(val)+int(p.val));}
	inline ModInt operator -(ModInt p){return ModInt(int(val)-int(p.val));}
	inline ModInt operator *(ModInt p){return ModInt(1ll*val*p.val);}
	inline ModInt QP(ll y){
		if(y<0)return inv().QP(-y);
		ModInt A=(*this),B=1U;
		for(;y;A=A*A,y>>=1)if(y&1)B=B*A;
		return B;
	}inline ModInt inv(){return QP(mod-2);}
	inline ModInt operator /(ModInt p){return (*this)*p.inv();}
	inline ModInt operator ^(ModInt p){return QP(p.val);}
	template<typename T>
	inline ModInt operator ^(T p){return QP(p);}

	template<typename T>
	inline ModInt operator +(T p){return (*this)+ModInt(p);}
	template<typename T>
	inline ModInt operator -(T p){return (*this)-ModInt(p);}
	template<typename T>
	inline ModInt operator *(T p){return (*this)*ModInt(p);}
	template<typename T>
	inline ModInt operator /(T p){return (*this)/ModInt(p);}

	inline ModInt operator +(){return (*this);}
	inline ModInt operator -(){return ModInt(0)-(*this);}

	template<typename T>
	inline friend ModInt operator +(T A,ModInt P){return ModInt(A)+P;}
	template<typename T>
	inline friend ModInt operator -(T A,ModInt P){return ModInt(A)-P;}
	template<typename T>
	inline friend ModInt operator *(T A,ModInt P){return ModInt(A)*P;}
	template<typename T>
	inline friend ModInt operator /(T A,ModInt P){return ModInt(A)/P;}

	inline void operator --(){val=(!val?mod-1:val-1);}
	inline void operator ++(){val=(val==mod-1?0:val+1);}

	inline void operator +=(ModInt P){(*this)=(*this)+P;}
	inline void operator -=(ModInt P){(*this)=(*this)-P;}
	inline void operator *=(ModInt P){(*this)=(*this)*P;}
	inline void operator /=(ModInt P){(*this)=(*this)/P;}

	template<typename T>
	inline void operator +=(T P){return (*this)=(*this)+ModInt(P);}
	template<typename T>
	inline void operator -=(T P){return (*this)=(*this)-ModInt(P);}
	template<typename T>
	inline void operator *=(T P){return (*this)=(*this)*ModInt(P);}
	template<typename T>
	inline void operator /=(T P){return (*this)=(*this)/ModInt(P);}
	template<typename T>
	inline void operator ^=(T P){return (*this)=(*this)^P;}

	U key(){return val;}
	inline bool operator == (ModInt P){return P.val==val;}
	inline bool operator != (ModInt P){return !((*this)==P);}

};
//=========================================================
namespace IO{
	const double eps=1e-8;
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char tmp[BUFSIZE];int cnt=0;
	inline char getch(){if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);return is==it?EOF:*is++;}
	int readInt(){int x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	ll readLL(){ll x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	Int readInt128(){Int x=0;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	char readChar(){char c=0;while(!c||c==' '||c=='\n')c=getch();return c;}
	std::string readString(){std::string S;char c=0;while(!c||c==' '||c=='\n')c=getch();while(c!=' '&&c!='\n')S.pd(c),c=getch();return S;}
	LD readDouble(){LD x=0,d=1;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();int cnt=0;bool flg=false;while(isdigit(c)){
		x=x*10+(c^48),flg|=(c^48),cnt+=flg,c=getch();if(cnt>=12)goto flg;}if(c=='.'){c=getch();while(isdigit(c)){d*=10,x+=(c^48)/d;flg|=(c^48),cnt+=flg;
		if(cnt>=12)goto flg;c=getch();}}flg:;return !y?x:-x;}
	ul readUll(){ul x=0;char c=0;while(!isdigit(c))c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return x;}

	void flush(){fwrite(tmp,1,cnt,stdout);cnt=0;}
	void putch(char c){tmp[cnt++]=c;if(cnt==BUFSIZE)flush();}
	void putint(int x){char Q[10];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putInt128(Int x){char Q[45];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putLL(ll x){char Q[20];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putString(std::string x){for(auto p:x)putch(p);}
	void putDouble(LD x){if(x<0)x=-x,putch('-');if(fabs(x)<=eps)return putch(0);bool flg=false;LD d=1e10;LD l=std::min(LD(1e-10),1.0/std::max(LD(1),x));
		while(d>=l){if(d<=1){if(ll(x/d+d*1e-2)%10>0||flg)putch(ll(x/d+d*1e-2)%10+'0'),flg=true;}else{if(ll(x/d)%10>0||flg)putch(ll(x/d)%10+'0'),flg=true;
		}x-=ll(x/d+eps)*d; if(d==1){if(!flg)putch('0');putch('.');}d/=10;}}
	void putUll(ul x){char Q[25];int tp=0;if(!x)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}

	struct Basic{
		Basic &operator>>(int &A){A=IO::readInt();return (*this);}
		Basic &operator>>(ll &A){A=IO::readLL();return (*this);}
		Basic &operator>>(Int &A){A=IO::readInt128();return (*this);}
		Basic &operator>>(char &A){A=IO::readChar();return (*this);}
		Basic &operator>>(std::string &A){A=IO::readString();return (*this);}
		Basic &operator>>(double &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(LD &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(float &A){A=IO::readDouble();return (*this);}
		template<typename T1,typename T2>
		Basic &operator>>(std::pair<T1,T2>&v){(*this)>>v.first>>v.second;return (*this);}
		template<typename T,int d>
		Basic &operator>>(std::array<T,d> &v){for(auto &p:v)(*this)>>p;return (*this);}
		template<typename T>
		Basic &operator>>(std::vector<T> &v){for(auto &p:v)(*this)>>p;return (*this);}
		Basic &operator>>(ul &v){v=readUll();return (*this);}

		Basic &operator<<(const int &A){putint(A);return (*this);}
		Basic &operator<<(const char &A){putch(A);return (*this);}
		Basic &operator<<(const ll &A){putLL(A);return (*this);}
		Basic &operator<<(const Int &A){putInt128(A);return (*this);}
		Basic &operator<<(const std::string &A){putString(A);return (*this);}
		Basic &operator<<(const LD &A){putDouble(A);return (*this);}
		Basic &operator<<(const double &A){putDouble(A);return (*this);}
		Basic &operator<<(const float &A){putDouble(A);return (*this);}
		template<typename T>
		Basic &operator<<(const std::vector<T> &v){for(int i=0;i<v.size();i++)(*this)<<v[i]<<(v.size()==i+1?'\n':' ');return (*this);}
		Basic &operator<<(const ul &A){putUll(A);return (*this);}

		void Flush(){flush();}
	}cin,cout;
}
//=========================================================
namespace Grader{
	std::vector<int>S;
	void Get(std::vector<int>v){
		assert(S.empty());

		reverse(all(S));
	}
	int readInt(){
		assert(!S.empty());
		int x=S.back();
		S.pop_back();
		return x;
	}
	void putInt(int x){
		std::vector<int>P;
		P.pd(x);Get(P);
	}void putVec(std::vector<int>v){Get(v);}
}
//=========================================================
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
//=========================================================
//const int mod=998244353;
//int add(int x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}
//int mul(int x,int y){return 1ll*x*y%mod;}
//void add(int &x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;}
const int N=2e5+10;
const int C1[2][4]={{1,1,2,2},{1,2,1,2}};
const int C2[3][3]={{0,1,1},{2,2,1},{2,1,2}};
const int C3[3][4]={{1,1,0,0},{1,2,1,2},{0,0,2,2}};
void Sub1(){
	IO::cout<<0<<'\n';
	IO::cout<<0<<'\n';
}
void Sub2(){
	IO::cout<<2<<'\n';
	IO::cout<<"0 1 1\n2 2 1\n2 1 2\n";
}
void Sub3(){
	IO::cout<<5<<'\n';
	IO::cout<<"0 1 1 2 2\n3 3 1 4 2\n3 1 3 2 4\n5 5 0 4 4\n5 0 5 0 0\n";
}
void Sub4(){
	IO::cout<<11<<'\n';
	IO::cout<<"0 1 1 2 2 3 3\n4 4 1 5 2 6 3\n4 1 4 2 5 3 6\n7 7 0 5 5 6 6\n7 0 7 0 0 8 8\n9 9 10 10 11 11 8\n9 10 9 10 11 8 11\n";
}
void Sub5(int n,ve<ve<int>>&v){
	int cnt=0;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=n;j+=4){
			for(int S1=i;S1<=i+1;S1++)
				for(int S2=j;S2<=j+3;S2++)
					v[S1][S2]=C1[S1-i][S2-j]+cnt;
			cnt+=2;
		}
	}
	IO::cout<<cnt<<'\n';
}
void Sub6(int n,ve<ve<int>>&v){
	int cnt=0;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=n-2;j+=4){
			for(int S1=i;S1<=i+1;S1++)
				for(int S2=j;S2<=j+3;S2++)
					v[S1][S2]=C1[S1-i][S2-j]+cnt;
			cnt+=2;
		}
	}
	for(int i=1;i<=n-2;i+=4){
		for(int S1=n-1;S1<=n;S1++)
			for(int S2=i;S2<=i+3;S2++)
				v[S2][S1]=C1[S1-(n-1)][S2-i]+cnt;
		cnt+=2;
	}
	IO::cout<<cnt<<'\n';
}
void copy(ve<ve<int>>&v,int x1,int y1,int opt,int r,int cnt){
	ve<ve<int>>S;
	if(opt==1){
		if(r&1^1){
			for(int i=0;i<2;i++){
				S.pd({});
				for(int j=0;j<4;j++)
					S.back().pd(C1[i][j]);
			}
		}else{
			for(int i=0;i<4;i++){
				S.pd({});
				for(int j=0;j<2;j++)
					S.back().pd(C1[j][i]);
			}
		}
	}if(opt==2){
		S=ve<ve<int>>(3,ve<int>(3));
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++)
				S[i][j]=C2[i][j];
		while(r--){
			auto P=S;
			for(int i=0;i<3;i++)
				for(int j=0;j<3;j++)
					S[j][2-i]=P[i][j];
		}
	}if(opt==3){
		if(r%4==0){
			S=ve<ve<int>>(3,ve<int>(4));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[i][j]=C3[i][j];
		}if(r%4==1){
			S=ve<ve<int>>(4,ve<int>(3));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[j][i]=C3[i][j];
		}if(r%4==2){
			S=ve<ve<int>>(3,ve<int>(4));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[2-i][j]=C3[i][j];
		}if(r%4==3){
			S=ve<ve<int>>(4,ve<int>(3));
			for(int i=0;i<3;i++)
				for(int j=0;j<4;j++)
					S[j][i]=C3[i][j];
		}
	}for(int i=x1;i<=x1+S.size()-1;i++)
		for(int j=y1;j<=y1+S[0].size()-1;j++)
			if(S[i-x1][j-y1]){
				if(v[i][j]){
					for(auto &p:S)IO::cout<<p;IO::cout.Flush(); 
					exit(0);
				}assert(!v[i][j]),v[i][j]=S[i-x1][j-y1]+cnt;
			}
				
}
void Sub7(int n,ve<ve<int>>&v){
	int cnt=0;
	auto get=[&](int x1,int y1,int x2,int y2,auto self)->void{
		if(x2-x1+1==9){
			copy(v,x1,y1,1,0,cnt);cnt+=2;
			copy(v,x1,y1+4,2,3,cnt);cnt+=2;
			copy(v,x1,y1+7,1,1,cnt);cnt+=2;
			copy(v,x1+2,y1,2,2,cnt);cnt+=2;
			copy(v,x1+2,y1+3,3,0,cnt);cnt+=2;
			copy(v,x1+4,y1+2,3,0,cnt);cnt+=2;
			copy(v,x1+5,y1,1,1,cnt);cnt+=2;
			copy(v,x1+6,y1+2,2,1,cnt);cnt+=2;
			copy(v,x1+7,y1+5,1,0,cnt);cnt+=2;
			copy(v,x1+4,y1+6,2,0,cnt);cnt+=2;
			return;
		};
		int L=x2-x1+1;
		if(L%4==3){
			self(x1,y1,x2-2,y2-2,self);
			for(int i=x1;i<=x2-3;i+=4)
				copy(v,i,y2-1,1,1,cnt),cnt+=2;
			for(int i=y1;i<=y2-3;i+=4)
				copy(v,x2-1,i,1,0,cnt),cnt+=2;
			copy(v,x2-2,y2-2,2,0,cnt),cnt+=2;
		}else{
			self(x1+2,y1,x2-2,y2-4,self);
			for(int i=y1;i<=y2-5;i+=4)
				copy(v,x1,i,1,0,cnt),cnt+=2,
				copy(v,x2-1,i,1,0,cnt),cnt+=2;
			copy(v,x1,y2-4,3,3,cnt),cnt+=2;
			copy(v,x1,y2-2,2,3,cnt),cnt+=2;
			copy(v,x2-2,y2-4,2,0,cnt),cnt+=2;
			copy(v,x2-3,y2-1,1,1,cnt),cnt+=2;
			copy(v,x2-5,y2-3,3,2,cnt),cnt+=2;
			for(int i=x1+4;!v[i][y2-3];i+=4){
				copy(v,i,y2-3,1,1,cnt),cnt+=2;
				copy(v,i-1,y2-1,1,1,cnt),cnt+=2;
			}
		}
	};
	get(1,1,n,n,get);
	IO::cout<<cnt<<'\n';
}
void solve(){
	//don't forget to open long long
	int n;IO::cin>>n;
	ve<ve<int>>v(n+1,ve<int>(n+1));
	auto write=[&]()->void{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				IO::cout<<v[i][j]<<char(j==n?'\n':' ');
	}; 
	if(n==1)Sub1();
	else if(n==3)Sub2();
	else if(n==5)Sub3(); 
	else if(n==7)Sub4();
	else if(n%4==0)Sub5(n,v),write();
	else if(n%4==2)Sub6(n,v),write();
	else Sub7(n,v),write();
	
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	//std::ios::sync_with_stdio(false);
	//std::cin.tie(0);
	//std::cout.tie(0);
	int T=1;IO::cin>>T; 
	while(T--)solve();

	IO::cout.Flush();
	return 0;
}
源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3788kb

input:

2
3
4

output:

2
0 1 1
2 2 1
2 1 2
4
1 1 2 2
1 2 1 2
3 3 4 4
3 4 3 4

result:

ok Correct. (2 test cases)

Test #2:

score: 0
Accepted
time: 86ms
memory: 5364kb

input:

246
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
...

output:

0
0
0
0 0
0 0
2
0 1 1
2 2 1
2 1 2
4
1 1 2 2
1 2 1 2
3 3 4 4
3 4 3 4
5
0 1 1 2 2
3 3 1 4 2
3 1 3 2 4
5 5 0 4 4
5 0 5 0 0
8
1 1 2 2 7 7
1 2 1 2 7 8
3 3 4 4 8 7
3 4 3 4 8 8
5 5 6 6 0 0
5 6 5 6 0 0
11
0 1 1 2 2 3 3
4 4 1 5 2 6 3
4 1 4 2 5 3 6
7 7 0 5 5 6 6
7 0 7 0 0 8 8
9 9 10 10 11 11 8
9 10 9 10 11 8 ...

result:

ok Correct. (246 test cases)

Test #3:

score: 0
Accepted
time: 81ms
memory: 5348kb

input:

64
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310

output:

15252
14521 14521 14522 14522 14525 14525 14526 14526 14529 14529 14530 14530 14533 14533 14534 14534 14537 14537 14538 14538 14541 14541 14542 14542 14545 14545 14546 14546 14549 14549 14550 14550 14553 14553 14554 14554 14557 14557 14558 14558 14561 14561 14562 14562 14565 14565 14566 14566 14569 ...

result:

ok Correct. (64 test cases)

Test #4:

score: 0
Accepted
time: 101ms
memory: 5416kb

input:

45
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355

output:

24180
23257 23257 23258 23258 23261 23261 23262 23262 23265 23265 23266 23266 23269 23269 23270 23270 23273 23273 23274 23274 23277 23277 23278 23278 23281 23281 23282 23282 23285 23285 23286 23286 23289 23289 23290 23290 23293 23293 23294 23294 23297 23297 23298 23298 23301 23301 23302 23302 23305 ...

result:

ok Correct. (45 test cases)

Test #5:

score: 0
Accepted
time: 107ms
memory: 5356kb

input:

35
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390

output:

31684
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...

result:

ok Correct. (35 test cases)

Test #6:

score: 0
Accepted
time: 104ms
memory: 5384kb

input:

30
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

output:

38220
37057 37057 37058 37058 37061 37061 37062 37062 37065 37065 37066 37066 37069 37069 37070 37070 37073 37073 37074 37074 37077 37077 37078 37078 37081 37081 37082 37082 37085 37085 37086 37086 37089 37089 37090 37090 37093 37093 37094 37094 37097 37097 37098 37098 37101 37101 37102 37102 37105 ...

result:

ok Correct. (30 test cases)

Test #7:

score: 0
Accepted
time: 34ms
memory: 20068kb

input:

2
2000
1000

output:

1000000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 5...

result:

ok Correct. (2 test cases)

Test #8:

score: 0
Accepted
time: 180ms
memory: 20080kb

input:

2
1999
999

output:

999000
993013 993013 993014 993014 993017 993017 993018 993018 993021 993021 993022 993022 993025 993025 993026 993026 993029 993029 993030 993030 993033 993033 993034 993034 993037 993037 993038 993038 993041 993041 993042 993042 993045 993045 993046 993046 993049 993049 993050 993050 993053 993053...

result:

ok Correct. (2 test cases)

Test #9:

score: 0
Accepted
time: 67ms
memory: 19760kb

input:

2
1998
998

output:

998000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #10:

score: 0
Accepted
time: 164ms
memory: 20044kb

input:

2
1997
997

output:

997002
993013 993013 993014 993014 993017 993017 993018 993018 993021 993021 993022 993022 993025 993025 993026 993026 993029 993029 993030 993030 993033 993033 993034 993034 993037 993037 993038 993038 993041 993041 993042 993042 993045 993045 993046 993046 993049 993049 993050 993050 993053 993053...

result:

ok Correct. (2 test cases)

Test #11:

score: 0
Accepted
time: 60ms
memory: 19776kb

input:

2
1996
996

output:

996004
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #12:

score: 0
Accepted
time: 146ms
memory: 19800kb

input:

2
1995
995

output:

995006
989031 989031 989032 989032 989035 989035 989036 989036 989039 989039 989040 989040 989043 989043 989044 989044 989047 989047 989048 989048 989051 989051 989052 989052 989055 989055 989056 989056 989059 989059 989060 989060 989063 989063 989064 989064 989067 989067 989068 989068 989071 989071...

result:

ok Correct. (2 test cases)

Test #13:

score: 0
Accepted
time: 66ms
memory: 19900kb

input:

2
1994
994

output:

994008
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #14:

score: 0
Accepted
time: 171ms
memory: 19916kb

input:

2
1993
993

output:

993012
989031 989031 989032 989032 989035 989035 989036 989036 989039 989039 989040 989040 989043 989043 989044 989044 989047 989047 989048 989048 989051 989051 989052 989052 989055 989055 989056 989056 989059 989059 989060 989060 989063 989063 989064 989064 989067 989067 989068 989068 989071 989071...

result:

ok Correct. (2 test cases)

Test #15:

score: 0
Accepted
time: 71ms
memory: 19840kb

input:

2
1992
992

output:

992016
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

result:

ok Correct. (2 test cases)

Test #16:

score: 0
Accepted
time: 171ms
memory: 19800kb

input:

2
1991
991

output:

991020
985057 985057 985058 985058 985061 985061 985062 985062 985065 985065 985066 985066 985069 985069 985070 985070 985073 985073 985074 985074 985077 985077 985078 985078 985081 985081 985082 985082 985085 985085 985086 985086 985089 985089 985090 985090 985093 985093 985094 985094 985097 985097...

result:

ok Correct. (2 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-03 00:42:48 | 开源项目