結果
問題 | 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 |
ソースコード
#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 1000000000000000000LLvoid 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&©[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;}