結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0