#1171799 (C++23) No.3593 I Love Sudoku

• 問題: No.3593 I Love Sudoku
• ユーザー: tkdgkb
• 提出日時: 2026-07-17 21:54:38
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,091 bytes
• コンパイル時間: 2,246 ms
• コンパイル使用メモリ: 343,280 KB
• 実行使用メモリ: 12,160 KB
• 最終ジャッジ日時: 2026-07-17 21:54:57
• 合計ジャッジ時間: 9,134 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
other	TLE * 1

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;

#define all(x) begin(x),end(x)
#define sz(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)

mt19937 rng(1337);

int a[9][9], b_arr[9][9];
int rb[9], rc[9], bb[9], bc[9];

vector<vi> gc, guc;

bool chk_a(int r, int c, int v) {
    rep(i,0,9) {
        if(a[r][i]==v) return 0;
        if(a[i][c]==v) return 0;
    }
    int br = r/3*3, bc = c/3*3;
    rep(i,0,3) rep(j,0,3) {
        if(a[br+i][bc+j]==v) return 0;
    }
    return 1;
}

bool gen_a(int r, int c) {
    if(r==9) return 1;
    int nr = c==8 ? r+1 : r;
    int nc = c==8 ? 0 : c+1;
    
    vi p(9);
    iota(all(p),0);
    shuffle(all(p),rng);
    
    for(int v : p) {
        if(chk_a(r,c,v)) {
            a[r][c] = v;
            if(gen_a(nr,nc)) return 1;
            a[r][c] = -1;
        }
    }
    return 0;
}

bool dfs_b(int c) {
    if(c==9) return 1;
    
    rep(idx,0,sz(gc)) {
        const auto& v = gc[idx];
        const auto& u = guc[idx];
        
        bool ok = 1;
        rep(i,0,9) {
            if(rb[i] & (1<<v[i])) {ok=0; break;}
            if(rc[i] & (1<<u[i])) {ok=0; break;}
            int blk = (i/3)*3 + (c/3);
            if(bb[blk] & (1<<v[i])) {ok=0; break;}
            if(bc[blk] & (1<<u[i])) {ok=0; break;}
        }
        if(!ok) continue;
        
        rep(i,0,9) {
            rb[i] |= (1<<v[i]);
            rc[i] |= (1<<u[i]);
            int blk = (i/3)*3 + (c/3);
            bb[blk] |= (1<<v[i]);
            bc[blk] |= (1<<u[i]);
            b_arr[i][c] = v[i];
        }
        
        if(dfs_b(c+1)) return 1;
        
        rep(i,0,9) {
            rb[i] &= ~(1<<v[i]);
            rc[i] &= ~(1<<u[i]);
            int blk = (i/3)*3 + (c/3);
            bb[blk] &= ~(1<<v[i]);
            bc[blk] &= ~(1<<u[i]);
        }
    }
    return 0;
}

void solve() {
    while(1) {
        rep(i,0,9) rep(j,0,9) a[i][j] = -1;
        gen_a(0,0);
        
        gc.clear();
        guc.clear();
        
        vi v(9);
        iota(all(v),0);
        do {
            vi u(9,0);
            rep(i,0,9) {
                rep(k,0,9) {
                    u[i] = (u[i] + a[i][k]*v[k])%9;
                }
            }
            int mk = 0;
            bool ok = 1;
            rep(i,0,9) {
                if(mk & (1<<u[i])) {ok=0; break;}
                mk |= (1<<u[i]);
            }
            if(ok) {
                gc.push_back(v);
                guc.push_back(u);
            }
        } while(next_permutation(all(v)));
        
        if(sz(gc) < 9) continue;
        
        rep(i,0,9) rb[i]=rc[i]=bb[i]=bc[i]=0;
        
        if(dfs_b(0)) {
            rep(i,0,9) {
                rep(j,0,9) cout << a[i][j] << (j==8?"":" ");
                cout << "\n";
            }
            rep(i,0,9) {
                rep(j,0,9) cout << b_arr[i][j] << (j==8?"":" ");
                cout << "\n";
            }
            return;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}