結果

問題 No.2958 Placing Many L-s
ユーザー 沙耶花沙耶花
提出日時 2024-11-08 22:32:15
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 214 ms / 2,000 ms
コード長 3,573 bytes
コンパイル時間 5,133 ms
コンパイル使用メモリ 268,480 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-11-08 22:32:26
合計ジャッジ時間 8,581 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 1000000000000000000LL

void dfs(vector<vector<int>> a,vector<vector<int>> xs,vector<vector<int>> ys,int cur){
	if(a.size()*a[0].size()%4==0&&cur > a.size()*a[0].size()/4){
		rep(i,a.size()){
			rep(j,a[i].size()){
				if(j!=0)cout<<' ';
				cout<<a[i][j];
			}
			cout<<endl;
		}
		exit(0);
	}
	int n = a.size();
	int m = a[0].size();
	pair<int,int> t = {Inf32,Inf32};
	rep(i,n){
		rep(j,m){
			if(a[i][j]==0){
				t = {i,j};
				break;
			}
		}
		if(t.first!=Inf32)break;
	}
	rep(i,n){
		rep(j,m){
			rep(k,xs.size()){
				auto copy = a;
				bool f  =true;
				rep(l,xs[k].size()){
					int xx = i+xs[k][l];
					int yy = j+ys[k][l];
					if(xx<0||xx>=n||yy<0||yy>=m){
						f = false;
						break;
					}
					if(copy[xx][yy]){
						f = false;
						break;
					}
					copy[xx][yy] = cur;
				}
				if(f&&copy[t.first][t.second]!=0){
					dfs(copy,xs,ys,cur+1);
				}
			}
			
		}
	}
}

vector<vector<int>> get(int n,int m){
	vector<vector<int>> t = {{0,0,0},{0,1,1},{2,2,1},{3,2,1},{3,2,4},{3,3,4},{5,4,4},{5,5,5}};
	int cur = 6;
	int xx = n;
	if(n==3)xx = m;
	while(t.size()!=xx){
		rep(i,8){
			t.push_back(t[i]);
			rep(j,t.back().size())t.back()[j] += cur;
		}
		cur += 6;
	}
		
	if(m==3)return t;
	vector<vector<int>> r(n,vector<int>(m));
	rep(i,n){
		rep(j,m){
			r[i][j] = t[j][i];
		}
	}
	return r;
	
}

int main(){
	/*
	
	vector<vector<int>> xs,ys;
	
	xs.push_back({0,1,2,2});
	ys.push_back({0,0,0,1});
	xs.push_back({0,0,0,1});
	ys.push_back({0,1,2,0});
	xs.push_back({0,0,1,2});
	ys.push_back({0,1,1,1});
	xs.push_back({0,1,1,1});
	ys.push_back({2,0,1,2});
	rep(i,4){
		xs.push_back(xs[i]);
		ys.push_back(ys[i]);
		int ma = 0;
		rep(j,xs[i].size())ma = max(ma,xs[i][j]);
		rep(j,xs[i].size())xs.back()[j] = ma-xs[i][j];
	}
	
	int n,m;
	cin>>n>>m;
	
	vector a(n,vector<int>(m));
	dfs(a,xs,ys,1);
	return 0;
	*/
	int _t;
	cin>>_t;
	
	
	
	rep(_,_t){
		int n,m;
		cin>>n>>m;
		if((n%4&&m%4)){
			cout<<-1<<endl;
			continue;
		}
		if(n==1||m==1){
			cout<<-1<<endl;
			continue;
		}
		if(n%2&&m%8){
			cout<<-1<<endl;
			continue;
		}
		if(m%2&&n%8){
			cout<<-1<<endl;
			continue;
		}
		cout<<(n*m)/4<<endl;
		int dx = 0,dy = 0;
		if(n%2){
			dx = 3;
			n -= 3;
		}
		else if(m%2){
			dy = 3;
			m -= 3;
		}
		int cur = 1;
		vector<vector<int>> a(n,vector<int>(m));
		if(m%4==0){
			for(int i=0;i<n;i+=2){
				for(int j=0;j<m;j+=4){
					a[i][j] = cur;
					a[i+1][j] = cur;
					a[i][j+1] = cur;
					a[i][j+2] = cur;
					cur++;
					a[i][j+3] = cur;
					a[i+1][j+1] = cur;
					a[i+1][j+2] = cur;
					a[i+1][j+3] = cur;
					cur++;
				}
			}
			
		}
		else{
			
			for(int i=0;i<n;i+=4){
				for(int j=0;j<m;j+=2){
					a[i+1][j] = cur;
					a[i+2][j] = cur;
					a[i+3][j] = cur;
					a[i+3][j+1] = cur;
					cur++;
					a[i][j] = cur;
					a[i][j+1] = cur;
					a[i+1][j+1] = cur;
					a[i+2][j+1] = cur;
					cur++;
				}
			}
		}
		if(dx>0){
			n += dx;
			auto r = get(dx,m);
			rep(i,r.size()){
				rep(j,r[i].size()){
					r[i][j] += cur;
				}
			}
			rep(j,r.size())a.push_back(r[j]);
		}
		else if(dy>0){
			m += dy;
			auto r = get(n,dy);
			rep(i,r.size()){
				rep(j,r[i].size()){
					r[i][j] += cur;
				}
			}
			rep(i,r.size()){
				rep(j,r[i].size()){
					a[i].push_back(r[i][j]);
				}
			}
		}
		rep(i,n){
			rep(j,m){
				if(j!=0)cout<<' ';
				cout<<a[i][j];
			}
			cout<<endl;
		}
	}
	
	return 0;
}
0