#1135835 (C++17) No.3335 ReCT

提出ソース
結果

問題	No.3335 ReCT
コンテスト
ユーザー	Sukyakura
提出日時	2025-11-22 01:58:35
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	15 ms / 2,000 ms
コード長	7,056 bytes
コンパイル時間	5,082 ms
コンパイル使用メモリ	273,232 KB
実行使用メモリ	7,720 KB
最終ジャッジ日時	2025-11-22 01:58:48
合計ジャッジ時間	11,889 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 97
権限があれば一括ダウンロードができます
ソースコード

raw source code
# include <bits/stdc++.h>
# include <atcoder/modint>
# include <atcoder/segtree>
# include <atcoder/lazysegtree>
# include <atcoder/dsu>
# include <atcoder/scc>
# include <atcoder/string>
# include <atcoder/twosat>
# include <atcoder/math>
# include <atcoder/convolution>
//# include <regex>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<long long> vl;
typedef vector<vector<long long>> vvl;
typedef vector<vector<vector<long long>>> vvvl;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,m,n) for(int i=m;i<n;i++)
#define repl(i,n) for(ll i=0;i<n;i++)
#define repsl(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define repsr(i,m,n) for(int i=n-1;i>=m;i--)
#define replr(i,n) for(ll i=n-1;i>=0;i--)
#define repslr(i,m,n) for(ll i=n-1;i>=m;i--)
#define sksort(x) sort(x.begin(), x.end())
#define sksortr(x) sort(x.rbegin(), x.rend())
#define disp(x) cout << x << endl
#define disps(x) cout << x << " "
#define dispe cout << endl
#define dispv(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj]);}dispe
#define dispvv(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispv(x[xqzi]);}
#define dispvm(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj].val());}dispe
#define dispvvm(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispvm(x[xqzi]);}
#define dispy cout << "Yes" << endl
#define dispn cout << "No" << endl
#define dispyn(x) if(x)dispy;else dispn
#define dispd cout << std::setprecision(20)
#define inp(x) int x;cin>>x
#define inpl(x) ll x;cin>>x
#define inps(x) string x;cin>>x
#define allv(x)  (x).begin(),(x).end()
#define allrv(x)  (x).rbegin(),(x).rend()
#define imax(x,y) x=max(x,y)
#define imin(x,y) x=min(x,y)
#define perm(x,y) vi permv(x);rep(permi,x)permv[permi]=permi;do y while(next_permutation(allv(permv)))
template <class T>
using priority_queue_asc = std::priority_queue<T,std::vector<T>,std::greater<T>>;
using mint = atcoder::modint998244353;
//using mint = atcoder::modint1000000007;

pair<int,vvi> C(int h, int w){
    bool f=false;
    if(h>w){
        swap(h,w);
        f=true;
    }
    if(h<=2||(h==3&&w%2==1))return {-1,{{}}};
    int c=0;
    vvi v(h,vi(w));
    if(h==3){
        vvi b={{0,1,1,1},{0,1,0,1},{0,0,0,1}};
        rep(i,w/4-1){
            rep(j,3)rep(k,4)v[j][i*4+k]=c+b[j][k]+1;
            c+=2;
        }
        if(w/2%2)b={{0,1,1,1,1,2},{0,1,0,2,1,2},{0,0,0,2,2,2}};
        rep(j,3)rep(k,4+w%4)v[j][(w/4-1)*4+k]=c+b[j][k]+1;
        c+=2+w/2%2;
    }else{
        vvi b(h,vi(4));
        rep(i,h-1)b[i][1]=1;
        b[0][2]=1;
        rep(i,h)b[i][3]=1;
        int p=2;
        rep(i,w/4-1){
            rep(j,h)rep(k,4)v[j][i*4+k]=c+b[j][k]+1;
            c+=p;
        }
        if(w%4==1){
            b=vvi(h,vi(5));
            rep(i,h-2)b[i+1][1]=1;
            b[1][2]=1;
            rep(i,h-2)b[i+1][3]=1;
            b[h-1][3]=2;
            rep(i,h)b[i][4]=2;
            rep(i,3)b[0][i+1]=2;
            p=3;
        }else if(w%4==2){
            b=vvi(h,vi(6));
            rep(i,h-1)b[i][1]=1;
            b[0][2]=1;
            b[0][3]=1;
            rep(i,h-1)b[i+1][3]=2;
            rep(i,h-1)b[i][4]=1;
            b[h-1][4]=2;
            rep(i,h)b[i][5]=2;
            p=3;
        }else if(w%4==3){
            b=vvi(h,vi(7));
            rep(i,h-1)b[i][1]=1;
            b[0][2]=1;
            b[0][3]=1;
            rep(i,h-2)b[i+1][3]=2;
            b[h-1][3]=3;
            rep(i,h-2)b[i][4]=1;
            b[h-2][4]=2;
            b[h-1][4]=3;
            b[0][5]=3;
            rep(i,h-2)b[i+1][5]=2;
            b[h-1][5]=3;
            rep(i,h)b[i][6]=3;
            p=4;
        }
        rep(j,h)rep(k,(int)b[j].size())v[j][(w/4-1)*4+k]=c+b[j][k]+1;
        c+=p;
    }
    if(f){
        vvi u(w,vi(h));
        rep(i,h)rep(j,w)u[j][i]=v[i][j];
        v=u;
    }
    return {c,v};
}

pair<int,vvi> T(int h, int w){
    bool f=false;
    if(h>w){
        swap(h,w);
        f=true;
    }
    if(h<=2||(h==3&&w<=5))return {-1,{{}}};
    int c=0;
    vvi v(h,vi(w));
    if(h==4&&w==4){
        v={{1,2,2,2},{1,1,2,4},{1,3,4,4},{3,3,3,4}};
        c=4;
    }else if(h==4&&w==5){
        v={{1,2,2,2,2},{1,1,1,2,4},{1,3,4,4,4},{3,3,3,3,4}};
        c=4;
    }else if(h==5&&w==5){
        v={{1,2,2,2,2},{1,1,1,2,4},{1,3,4,4,4},{3,3,3,5,4},{5,5,5,5,5}};
        c=5;
    }else{
        vvi b(3,vi(w));
        rep(i,w-2)b[0][i+1]=1;
        rep(i,w-2)b[2][i+1]=2;
        rep(i,3)b[1][w-i-2]=3-i;
        rep(i,3)b[i][w-1]=3;
        int p=4;
        rep(i,h/3-1){
            rep(j,3)rep(k,w)v[i*3+j][k]=c+b[j][k]+1;
            c+=p;
        }
        if(h%3==1){
            b=vvi(4,vi(w));
            rep(i,w-1)b[0][i+1]=1;
            b[1][w-2]=1;
            b[1][w-1]=2;
            b[2][1]=3;
            rep(i,w-2)b[2][i+2]=2;
            rep(i,w-1)b[3][i]=3;
            b[3][w-1]=2;
            p=4;
        }else if(h%3==2){
            b=vvi(5,vi(w));
            rep(i,w-1)b[0][i+1]=1;
            b[1][w-2]=1;
            b[1][w-1]=2;
            b[2][1]=3;
            rep(i,w-2)b[2][i+2]=2;
            rep(i,w-2)b[3][i]=3;
            b[3][w-2]=4;
            b[3][w-1]=2;
            rep(i,w)b[4][i]=4;
            p=5;
        }
        rep(j,(int)b.size())rep(k,w)v[(h/3-1)*3+j][k]=c+b[j][k]+1;
        c+=p;
    }
    if(f){
        vvi u(w,vi(h));
        rep(i,h)rep(j,w)u[j][i]=v[i][j];
        v=u;
    }
    return {c,v};
}

pair<int,vvi> CT(int h, int w){
    bool f=false;
    if(h>w){
        swap(h,w);
        f=true;
    }
    if(h<=2)return {-1,{{}}};
    int c=0;
    vvi v(h,vi(w));
    if(h==3&&w==3){
        v={{1,2,2},{1,1,2},{1,2,2}};
        c=2;
    }else{
        vvi b(3,vi(w));
        rep(i,w-1)b[0][i+1]=1;
        b[1][w-1]=1;
        rep(i,w-1)b[2][i+1]=1;
        int p=2;
        rep(i,h/3-1){
            rep(j,3)rep(k,w)v[i*3+j][k]=c+b[j][k]+1;
            c+=p;
        }
        if(h%3==1){
            b=vvi(4,vi(w));
            b[0][w-1]=1;
            rep(i,w-1)b[1][i+1]=1;
            b[2][w-2]=2;
            b[2][w-1]=1;
            rep(i,w)b[3][i]=2;
            p=3;
        }else if(h%3==2){
            b=vvi(5,vi(w));
            rep(i,w-2)b[1][i+1]=1;
            b[1][w-1]=2;
            b[2][1]=1;
            rep(i,w-2)b[2][i+2]=2;
            rep(i,w-2)b[3][i+1]=1;
            b[3][w-1]=2;
            p=3;
        }
        rep(j,(int)b.size())rep(k,w)v[(h/3-1)*3+j][k]=c+b[j][k]+1;
        c+=p;
    }
    if(f){
        vvi u(w,vi(h));
        rep(i,h)rep(j,w)u[j][i]=v[i][j];
        v=u;
    }
    return {c,v};
}

int main(){
    inp(h);
    inp(w);
    pair<int,vvi> pc=C(h,w);
    disp(pc.first);
    if(pc.first!=-1)dispvv(pc.second);
    pair<int,vvi> pt=T(h,w);
    disp(pt.first);
    if(pt.first!=-1)dispvv(pt.second);
    pair<int,vvi> pct=CT(h,w);
    disp(pct.first);
    if(pct.first!=-1)dispvv(pct.second);
}
yukicoder

結果

ソースコード
