#741853 (C++17) No.1851 Regular Tiling

• 問題: No.1851 Regular Tiling
• ユーザー: %20
• 提出日時: 2022-02-25 21:47:06
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 63 ms / 2,000 ms
• コード長: 16,479 bytes
• コンパイル時間: 2,828 ms
• コンパイル使用メモリ: 221,432 KB
• 最終ジャッジ日時: 2025-01-28 01:59:39
• ジャッジサーバーID （参考情報）: judge4 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 14

ソースコード

#if 0
__END__
#endif
#include<bits/stdc++.h>
#define fr(i,n) for(int i=0;i<(n);++i)
#define foor(i,a,b) for(int i=(a);i<=(b);++i)
#define rf(i,n) for(int i=(n);i-->0;)
#define roof(i,b,a) for(int i=(b);i>=(a);--i)
#define elsif else if
#define all(x) x.begin(),x.end()
#define Sort(x) sort(all(x))
#define Reverse(x) reverse(all(x))
#define Rev(x) reverse(all(x))
#define Unique(v) v.erase(unique(all(v)),v.end())
#define PQ priority_queue
#define NP(x) next_permutation(all(x))
#define M_PI 3.14159265358979323846
#define popcount __builtin_popcountll
using namespace std;         using  vb=vector<bool>;using vvb=vector<vb>;
                             using   vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using  ll=long long;         using   vl=vector< ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using ull=unsigned long long;using   vu=vector<ull>;using vvu=vector<vu>;
using dbl=double;            using   vd=vector<dbl>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using str=string;            using   vs=vector<str>;using vvs=vector<vs>;
using pii=pair<int,int>;     using vpii=vector<pii>;using mii=map<int,int>;
using pll=pair< ll, ll>;     using vpll=vector<pll>;using mll=map< ll, ll>;
using pdd=pair<dbl,dbl>;     using vpdd=vector<pdd>;using mdd=map<dbl,dbl>;
using pss=pair<str,str>;     using vpss=vector<pss>;using mss=map<str,str>;
using pil=pair<int, ll>;     using vpil=vector<pil>;using mil=map<int, ll>;
using pli=pair< ll,int>;     using vpli=vector<pli>;using mli=map< ll,int>;
using pdi=pair<dbl,int>;     using vpdi=vector<pdi>;using mdi=map<dbl,int>;
template<typename T>vector<T>&operator<<(vector<T>&v,const T t){v.push_back(t);return v;}
template<typename T>multiset<T>&operator<<(multiset<T>&m,const T t){m.insert(t);return m;}
template<typename T>set<T>&operator<<(set<T>&s,const T t){s.insert(t);return s;}
template<typename T>stack<T>&operator<<(stack<T>&s,const T t){s.push(t);return s;}
template<typename T>stack<T>&operator>>(stack<T>&s,T&t){t=s.top();s.pop();return s;}
template<typename T>queue<T>&operator<<(queue<T>&q,const T t){q.push(t);return q;}
template<typename T>queue<T>&operator>>(queue<T>&q,T&t){t=q.front();q.pop();return q;}
template<typename T,typename U>PQ<T,vector<T>,U>&operator<<(PQ<T,vector<T>,U>&q,const T t){q.push(t);return q;}
template<typename T,typename U>PQ<T,vector<T>,U>&operator>>(PQ<T,vector<T>,U>&q,T&t){t=q.top();q.pop();return q;}
template<typename T,typename U>istream&operator>>(istream&s,pair<T,U>&p){return s>>p.first>>p.second;}
istream&operator>>(istream&s,_Bit_reference b){int a;s>>a;assert(a==0||a==1);b=a;return s;}
template<typename T>istream&operator>>(istream&s,vector<T>&v){fr(i,v.size()){s>>v[i];}return s;}
template<typename T,typename U>ostream&operator<<(ostream&s,const pair<T,U>p){return s<<p.first<<" "<<p.second;}
template<typename T>ostream&operator<<(ostream&s,const vector<T>v){fr(i,v.size()){i?s<<" "<<v[i]:s<<v[i];}return s;}
template<typename T>ostream&operator<<(ostream&s,const deque<T>d){fr(i,d.size()){i?s<<" "<<d[i]:s<<d[i];}return s;}
template<typename T>_Bit_reference operator&=(_Bit_reference b,T t){return b=b&t;}
template<typename T>_Bit_reference operator^=(_Bit_reference b,T t){return b=b^t;}
template<typename T>_Bit_reference operator|=(_Bit_reference b,T t){return b=b|t;}
template<typename T,typename U>pair<T,U>operator+(pair<T,U>a,pair<T,U>b){return {a.first+b.first,a.second+b.second};}
template<typename T,typename U>pair<T,U>operator-(pair<T,U>a,pair<T,U>b){return {a.first-b.first,a.second-b.second};}
template<typename T,typename U>pair<T,U>&operator+=(pair<T,U>&a,pair<T,U>b){return a=a+b;}
template<typename T,typename U>pair<T,U>&operator-=(pair<T,U>&a,pair<T,U>b){return a=a-b;}
void print(void){cout<<"\n";}
void Print(void){cout<<endl;}
template<typename T>void print(T t){cout<<t<<"\n";}
template<typename T>void Print(T t){cout<<t<<endl;}
template<typename T,typename...U>void print(T&&t,U&&...u){cout<<t<<" ";print(forward<U>(u)...);}
template<typename T,typename...U>void Print(T&&t,U&&...u){cout<<t<<" ";Print(forward<U>(u)...);}
bool YN(bool b){print(b?"YES":"NO");return b;}bool PI(bool b){print(b?"POSSIBLE":"IMPOSSIBLE");return b;}
bool Yn(bool b){print(b?"Yes":"No");return b;}bool Pi(bool b){print(b?"Possible":"Impossible");return b;}
bool yn(bool b){print(b?"yes":"no");return b;}bool pi(bool b){print(b?"possible":"impossible");return b;}
const int e5=1e5;
const int e9=1e9;
const int MD=1e9+7;
const int md=998244353;
const ll e18=1e18;
template<typename T>str to_string(const T&n){ostringstream s;s<<n;return s.str();}
template<typename T>bool chmax(T&a,T b){return a<b?(a=b,true):false;}
template<typename T>bool chmin(T&a,T b){return a>b?(a=b,true):false;}
template<typename T,typename U>vector<pair<T,U>>dijkstra(const vector<vector<pair<T,U>>>&E,const U s,const T inf){using P=pair<T,U>;vector<P>d;fr(i,E.size()){d<<P{inf,i};}PQ<P,vector<P>,greater<P>>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.first<d[e.second].first){d[e.second]=P{d[v].first+e.first,v};pq<<P{d[v].first+e.first,e.second};}}}}return d;}
//template<typename T,typename U>map<U,pair<T,U>>dijkstra(map<U,vector<pair<T,U>>>E,const U s,const T inf){using P=pair<T,U>;map<U,P>d;for(pair<U,vector<P>>e:E){d[e.first]=P{inf,e.first};}PQ<P,vector<P>,greater<P>>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.first<d[e.second].first){d[e.second]=P{d[v].first+e.first,v};pq<<P{d[v].first+e.first,e.second};}}}}return d;}
//ll maxflow(vector<mil>&E,int s,int t){ll z=0;vi b(E.size(),-1);for(int i=0;;++i){static auto dfs=[&](int v,ll f,auto&dfs)->ll{if(v==t)return f;b[v]=i;for(auto&p:E[v]){if(b[p.first]<i&&p.second){if(ll r=dfs(p.first,min(f,p.second),dfs)){p.second-=r;E[p.first][v]+=r;return r;}}}return 0;};ll x=dfs(s,ll(1e18),dfs);z+=x;if(x==0)return z;}}
template<typename T>T distsq(pair<T,T>a,pair<T,T>b){return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);}
template<typename T>T max(const vector<T>a){assert(a.size());T m=a[0];for(T e:a){m=max(m,e);}return m;}
template<typename T>T min(const vector<T>a){assert(a.size());T m=a[0];for(T e:a){m=min(m,e);}return m;}
template<typename T>T gcd(const T a,const T b){return a?gcd(b%a,a):b;}
template<typename T>T gcd(const vector<T>a){T g=a[0];for(T e:a){g=gcd(g,e);}return g;}
//template<typename T>vector<T>LCS(vector<T>A,vector<T>B){int N=A.size(),M=B.size();vector<vector<pair<int,pii>>>d(N+1,vector<pair<int,pii>>(M+1));fr(i,N){fr(j,M){if(A[i]==B[j]){d[i+1][j+1]={d[i][j].first+1,{i,j}};}else{d[i+1][j+1]=max(d[i][j+1],d[i+1][j]);}}}vector<T>r;for(pii p={N,M};d[p.first][p.second].first;p=d[p.first][p.second].second){r<<A[d[p.first][p.second].second.first];}Reverse(r);return r;}
//str LCS(str S,str T){vector<char>s=LCS(vector<char>(S.begin(),S.end()),vector<char>(T.begin(),T.end()));return str(s.begin(),s.end());}
//template<typename T>vector<pair<T,T>>ConvexHull(vector<pair<T,T>>V){if(V.size()<=3){return V;}Sort(V);rf(i,V.size()-1)V<<V[i];vector<pair<T,T>>r;for(pair<T,T>p:V){int s=r.size();while(s>=2&&(p.second-r[s-1].second)*(p.first-r[s-2].first)<(p.second-r[s-2].second)*(p.first-r[s-1].first)){r.pop_back();--s;}r<<p;}r.pop_back();return r;}
class UnionFind{vi p,s;void extend(int N){foor(i,p.size(),N){p<<i;s<<1;}}public:UnionFind(void){}UnionFind(int N){extend(N-1);}int find(int i){extend(i);return p[i]=p[i]==i?i:find(p[i]);}void unite(int a,int b){extend(a);extend(b);if((a=find(a))!=(b=find(b))){if(s[a]>s[b]){swap(a,b);}s[b]+=s[a];p[a]=b;}}void unite(pii p){return unite(p.first,p.second);}bool same(int a,int b){extend(a);extend(b);return find(a)==find(b);}bool same(pii p){return same(p.first,p.second);}int size(int x){extend(x);return s[find(x)];}};
//ll MST(vector<pair<ll,pii>>&E){Sort(E);UnionFind uf;ll z=0;for(auto&e:E){if(!uf.same(e.second)){z+=e.first;uf.unite(e.second);}}return z;}
//ll strmod(const str&s,const int m){ll x=0;fr(i,s.size()){x=(x*10+s[i]-48)%m;}return x;}
vvl mul(const vvl&A,const vvl&B,const int m){vvl C;fr(y,A.size()){C<<vl(B[y].size());}fr(y,C.size()){fr(x,C[y].size()){fr(i,A[0].size()){(C[y][x]+=A[y][i]*B[i][x])%=m;}}}return C;}
vvl pow(const vvl&A,const ll n,const int m){vvl B;fr(y,A.size()){B<<vl(A.size());}if(n==0){fr(i,B.size()){B[i][i]=1;}}elsif(n%2){B=mul(A,pow(A,n-1,m),m);}else{vvl C=pow(A,n/2,m);B=mul(C,C,m);}return B;}
ll pow(const ll a,const ll n,const int m){ll t;return n?(n&1?a>=0?a%m:(m-(-a%m))%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:1;}
ll inv(const ll x,const int p){assert(x!=0);return pow(x,p-2,p);}
//ll inv(const ll x){return inv(x,MD);}
vpll fact(const int n,const int p){assert(n<p);vpll v(n+1);v[0].first=1;foor(i,1,n){v[i].first=v[i-1].first*i%p;}v[n].second=inv(v[n].first,p);roof(i,n,1){v[i-1].second=v[i].second*i%p;}return v;}
class Combination{const vpll f;const int M;public:Combination(int n,int m):f(fact(n,m)),M(m){}ll P(int n,int k){return n<0||k<0||n<k?0ll:f[n].first*f[n-k].second%M;}ll C(int n,int k){return k<0||n<k?0ll:P(n,k)*f[k].second%M;}ll H(int n,int k){return n==0&&k==0?1ll:C(n+k-1,k);}ll F(int n){return n<0?0:f[n].first;}};
ll C2(const int n){return(ll)n*~-n/2;}
ll sum(const vi a){ll s=0;for(int e:a){s+=e;}return s;}
ll sum(const vl a){ll s=0;for(ll e:a){s+=e;}return s;}
ll sum(const vb a){ll s=0;for(bool e:a){s+=e;}return s;}
template<typename T>int MSB(T N){int r=-1;for(;N>0;N/=2){++r;}return r;}
template<typename T>class SegmentTree{vector<T>S;T(*const op)(T a,T b);const T zero;const int B;public:SegmentTree(int N,T(*f)(T a,T b),const T zero):S(1<<MSB(N-1)+2,zero),op(f),zero(zero),B(1<<MSB(N-1)+1){}SegmentTree(vector<T>v,T(*f)(T a,T b),const T zero):SegmentTree(v.size(),f,zero){fr(i,v.size()){S[S.size()/2+i]=v[i];}roof(i,S.size()/2-1,1){S[i]=op(S[i*2],S[i*2+1]);}}T calc(int l,int r){l+=B;r+=B;if(l>r){return zero;}if(l==r){return S[l];}T L=S[l],R=S[r];for(;l/2<r/2;l/=2,r/=2){if(l%2==0){L=op(L,S[l+1]);}if(r%2==1){R=op(S[r-1],R);}}return op(L,R);}void replace(int i,T x){for(S[i+=B]=x;i!=1;i/=2){if(i%2){S[i/2]=op(S[i-1],S[i]);}else{S[i/2]=op(S[i],S[i+1]);}}}void add(int i,T x){replace(i,op(S[B+i],x));}T top(){return S[1];}T get(int i){return S[i+B];}};
//ll BITsum(vl&B,int i){ll z=0;while(i>0){z+=B[i];i-=i&-i;}return z;}
//void BITadd(vl&B,int i,ll x){while(i<B.size()){B[i]+=x;i+=i&-i;}}
//ll fib(const ll n,const int m){ll a,b,c,d,A,B,C,D;a=1;b=0;c=0;d=1;rf(i,63){A=a*a+b*c;B=a*b+b*d;C=c*a+d*c;D=c*b+d*d;if(n>>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;}
vi primes(int n){vb b(n+1);vi p;foor(i,2,n){if(!b[i]){p<<i;for(int j=2*i;j<=n;j+=i){b[j]=true;}}}return p;}
//vl primes(ll L,ll R){assert(0<=L);assert(L<=R);int n=sqrt(R);vb b(n+1,true),B(R-L+1,true);for(ll i=2;i<=n;++i){if(b[i]){for(ll j=i+i;j<=n;j+=i){b[j]=false;}for(ll j=R/i*i;j>=L;j-=i){B[j-L]=false;}}}vl P;for(ll i=max(2ll,L);i<=R;++i){if(B[i-L]){P<<i;}}return P;}
vb isprime(const int n){vb v(n+1,true);v[0]=v[1]=false;foor(i,2,n){if(v[i]){for(int j=2*i;j<=n;j+=i){v[j]=false;}}}return v;}
//class LCA{vvi par;vi dep;public:LCA(vvi&E,int root):par(MSB(E.size())+1,vi(E.size())),dep(E.size()){function<void(int,int)>dfs=[&](int i,int p){for(int j:E[i])if(j!=p){par[0][j]=i;dep[j]=dep[i]+1;dfs(j,i);}};par[0][root]=root;dfs(root,root);fr(i,par.size()-1){fr(j,par[0].size()){par[i+1][j]=par[i][par[i][j]];}}}int operator()(int a,int b){if(dep[a]>dep[b])swap(a,b);for(int t=dep[b]-dep[a],i=0;t;t>>=1,++i){if(t&1){b=par[i][b];}}if(a==b)return a;rf(i,par.size()){if(par[i][a]!=par[i][b]){a=par[i][a];b=par[i][b];}}return par[0][a];}int dist(int a,int b){return dep[a]+dep[b]-2*dep[operator()(a,b)];}};
vpli factor(ll N){vpli r;for(ll i=2;i*i<=N;++i){if(N%i==0){r<<pli{i,0};while(N%i==0){N/=i;++r.back().second;}}}if(N>1){r<<pli{N,1};}return r;}
vl divisors(ll n){vl r;ll m=sqrt(n);foor(i,1,m)if(n%i==0)r<<ll(i);rf(i,r.size()-(m*m==n))r<<n/r[i];return r;}
//vi SuffixArray(str S){int N=S.size();vi rank(N+1),tmp(N+1),sa(N+1);fr(i,N){sa[i]=i;rank[i]=S[i];}sa[N]=N;rank[N]=-1;int k;auto cmp=[&](int&a,int&b)->bool{if(rank[a]!=rank[b])return rank[a]<rank[b];return (a+k<=N?rank[a+k]:-1)<(b+k<=N?rank[b+k]:-1);};for(k=1;k<=N;k*=2){sort(all(sa),cmp);tmp[sa[0]]=0;foor(i,1,N){tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);}rank=tmp;}return sa;};
template<typename T,typename U>void sort2(vector<T>&a,vector<U>&b){int N=a.size();assert(b.size()==N);vector<pair<T,U>>v;fr(i,N){v<<pair<T,U>{a[i],b[i]};}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second;}}
template<typename T,typename U,typename V>void sort3(vector<T>&a,vector<U>&b,vector<V>&c){int N=a.size();assert(b.size()==N);assert(c.size()==N);vector<pair<T,pair<U,V>>>v;fr(i,N){v.push_back({a[i],{b[i],c[i]}});}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second.first;c[i]=v[i].second.second;}}
vi toposo(vvi E){int N=E.size();vi T(N,-1);{vvi R(N);vi v;{vb u(N);function<void(int)>f=[&](int i){if(u[i])return;u[i]=true;for(int j:E[i]){R[j]<<i;f(j);}v<<i;};fr(i,N){f(i);}}{int k=0;function<void(int)>f=[&](int i){T[i]=k;for(int j:R[i]){if(T[j]==-1){f(j);}}};rf(i,v.size()){if(T[v[i]]==-1){f(v[i]);++k;}}}}return T;}
//vb SAT2(vvi E){int N=E.size();assert(N%2==0);vi T=toposo(E);vb z(N);fr(i,N/2){if(T[2*i]==T[2*i+1]){return vb{};}z[2*i+(T[2*i]<T[2*i+1])]=true;}return z;}
//ll extgcd(ll a,ll b,ll&x,ll&y){if(b==0){x=1;y=0;return a;}ll d=extgcd(b,a%b,y,x);y-=a/b*x;return d;}
//ll INV(ll a,ll m){ll x,y;extgcd(a,m,x,y);return (x%m+m)%m;}
//ll garner(int m1,int a1,int m2,int a2){if(a1>a2){swap(a1,a2);swap(m1,m2);}return INV(m1,m2)*(a2-a1)%m2*m1+a1;}
//ull mulull(ull a,ull b,ull m){using ld=long double;ll t=a*b-m*ull(ld(a)*ld(b)/ld(m));return t+m*(t<0)-m*(t>=ll(m));}
//ll powll(const ll a,const ll n,const ll m){return n?n%2?mulull(a,powll(a,n-1,m),m):powll(mulull(a,a,m),n/2,m):1;}
//bool MillerRabin(int n){if(n<2){return false;}int d=n-1,s=0;for(;d%2==0;d/=2){++s;}if(s==0){return n==2;}for(int a:{2,7,61})if(a<n){if(pow(a,d,n)!=1){fr(r,s){if(pow(a,d<<r,n)==n-1)break;if(r==s-1)return false;}}}return true;}
//bool MillerRabin(ll n){if(n<1ll<<31){return MillerRabin(int(n));}if(n<2){return false;}ll d=n-1;int s=0;for(;d%2==0;d/=2){++s;}if(s==0){return n==2;}for(int a:{2,325,9375,28178,450775,9780504,1795265022})if(a<n){if(powll(a,d,n)!=1){fr(r,s){if(powll(a,d<<r,n)==n-1)break;if(r==s-1)return false;}}}return true;}
//class Prime{vi P,mf;public:Prime(int N):mf(N+1){foor(i,2,N){if(mf[i]==0){mf[i]=i;P<<i;}for(int j=0;j<P.size()&&i*P[j]<=N&&P[j]<=mf[i];++j){mf[i*P[j]]=P[j];}}}vi list(void){return P;}bool isprime(int x){assert(x<int(mf.size()));return x>=2&&mf[x]==x;}int minfactor(int x){assert(x>=2);assert(x<int(mf.size()));return mf[x];}vpii factor(int x){assert(x>=1);assert(x<int(mf.size()));vpii v;while(x>1){if(v.empty()||v.back().first<mf[x]){v<<pii{mf[x],1};}else{++v.back().second;}x=x/mf[x];}return v;}vi divisors(int x){assert(x>=1);assert(x<int(mf.size()));vi v={1};for(pii p:factor(x)){int n=v.size();fr(i,n){int t=v[i];fr(_,p.second){t*=p.first;v<<t;}}}Sort(v);return v;}};
//int TonelliShanks(const int p,const int a){assert(0<=a&&a<p);if(p==2||a==0)return a;if(pow(a,(p-1)/2,p)!=1)return -1;if(p%4==3)return pow(a,(p+1)/4,p);random_device rand;int q=p-1,m=0;for(;q%2==0;q/=2){++m;}int z;do{z=rand()%p;}while(pow(z,(p-1)/2,p)!=p-1);int c=pow(z,q,p),t=pow(a,q,p),r=pow(a,(q+1)/2,p);for(;m>1;--m){if(pow(t,1<<m-2,p)==1){c=ll(c)*c%p;}else{r=ll(c)*r%p;c=ll(c)*c%p;t=ll(c)*t%p;}}return r;}
vi BFS(vvi&E,int s){vi d(E.size(),-1);d[s]=0;queue<int>q;q<<s;while(q.size()){int i;q>>i;for(int j:E[i]){if(d[j]<0){d[j]=d[i]+1;q<<j;}}}return d;}
//template<typename T>vector<T>slidemax(const vector<T>&v,int k){assert(1<=k&&k<=int(v.size()));--k;vector<T>d(v.size()-k);deque<int>q;fr(j,k){while(q.size()&&v[q.back()]<=v[j]){q.pop_back();}q.push_back(j);}fr(j,v.size()-k){while(q.size()&&v[q.back()]<=v[j+k]){q.pop_back();}q.push_back(j+k);d[j]=v[q.front()];if(q.front()==j){q.pop_front();}}return d;}

int f(int n,int i){
	return i%3==(n%3==1?0:2);
}

int main(){cin.tie(0);ios::sync_with_stdio(false);
	int Q;cin>>Q;
	fr(_,Q){
		int H,W;cin>>H>>W;
		fr(i,H){
			fr(j,W){
				cout<<2-f(H,i)-f(W,j)<<" \n"[j==W-1];
			}
		}
	}
	return 0;
}

#if 0
0 11 110 0110 11011 110110

  22 221 1221 22122 221221
  22 221 1221 22122 221221

     221 1221 22122 221221
     221 1221 22122 221221
     110 0110 11011 110110

         0110 11011 110110
         1221 22122 221221
         1221 22122 221221
         0110 11011 110110
#endif