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

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

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define all(x) begin(x),end(x)
#define sz(x) (int)x.size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

vector<vi> gc, guc;
int step_cnt = 0;

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;
    int b_id = (r / 3) * 3 + (c / 3);
    
    int used = ra[r] | ca[c] | ba[b_id];
    if(used == 511) return 0;
    
    vi p;
    for(int i = 0; i < 9; i++) {
        if(!(used & (1 << i))) p.push_back(i);
    }
    shuffle(all(p), rng);
    
    for(int v : p) {
        a[r][c] = v;
        ra[r] |= (1 << v); ca[c] |= (1 << v); ba[b_id] |= (1 << v);
        if(gen_a(nr, nc)) return 1;
        ra[r] ^= (1 << v); ca[c] ^= (1 << v); ba[b_id] ^= (1 << v);
    }
    return 0;
}

bool dfs_b(int c, const vi& p) {
    if(c == 9) return 1;
    if(++step_cnt > 2500) return 0;
    
    for(int id : p) {
        const auto& v = gc[id];
        const auto& u = guc[id];
        
        bool ok = 1;
        for(int i = 0; i < 9; i++) {
            if(rb[i] & (1 << v[i])) { ok = 0; break; }
            if(rc[i] & (1 << u[i])) { ok = 0; break; }
            int b_id = (i / 3) * 3 + (c / 3);
            if(bb[b_id] & (1 << v[i])) { ok = 0; break; }
            if(bc[b_id] & (1 << u[i])) { ok = 0; break; }
        }
        if(!ok) continue;
        
        for(int i = 0; i < 9; i++) {
            rb[i] |= (1 << v[i]);
            rc[i] |= (1 << u[i]);
            int b_id = (i / 3) * 3 + (c / 3);
            bb[b_id] |= (1 << v[i]);
            bc[b_id] |= (1 << u[i]);
            b_arr[i][c] = v[i];
        }
        
        if(dfs_b(c + 1, p)) return 1;
        
        for(int i = 0; i < 9; i++) {
            rb[i] ^= (1 << v[i]);
            rc[i] ^= (1 << u[i]);
            int b_id = (i / 3) * 3 + (c / 3);
            bb[b_id] ^= (1 << v[i]);
            bc[b_id] ^= (1 << u[i]);
        }
    }
    return 0;
}

void solve() {
    vi v(9); 
    while(1) {
        for(int i = 0; i < 9; i++) ra[i] = ca[i] = ba[i] = 0;
        gen_a(0, 0);
        
        gc.clear();
        guc.clear();
        
        iota(all(v), 0);
        do {
            int v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3], v4 = v[4], v5 = v[5], v6 = v[6], v7 = v[7], v8 = v[8];
            int mk = 0;
            bool ok = 1;
            int u_cur[9];
            
            for(int i = 0; i < 9; i++) {
                int sum = a[i][0] * v0 + a[i][1] * v1 + a[i][2] * v2 + 
                          a[i][3] * v3 + a[i][4] * v4 + a[i][5] * v5 + 
                          a[i][6] * v6 + a[i][7] * v7 + a[i][8] * v8;
                sum %= 9;
                if(mk & (1 << sum)) { ok = 0; break; }
                mk |= (1 << sum);
                u_cur[i] = sum;
            }
            
            if(ok) {
                gc.push_back(v);
                guc.push_back(vi(u_cur, u_cur + 9));
            }
        } while(next_permutation(all(v)));
        
        if(sz(gc) < 9) continue;
        
        for(int i = 0; i < 9; i++) rb[i] = rc[i] = bb[i] = bc[i] = 0;
        
        vi p(sz(gc));
        iota(all(p), 0);
        shuffle(all(p), rng);
        
        step_cnt = 0;
        if(dfs_b(0, p)) {
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) cout << a[i][j] << (j == 8 ? "" : " ");
                cout << "\n";
            }
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) cout << b_arr[i][j] << (j == 8 ? "" : " ");
                cout << "\n";
            }
            return;
        }
    }
}

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