Submission #1369398


Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
constexpr long long mod = 1'000'000'007;

int expand(int mask, const vector<int> &unzip){
    int emask = 0;
    for (int i = 0; i != unzip.size(); ++i){
        if ((mask & (1 << i)) != 0){
            emask |= (1 << unzip[i]);
        }
    }
    return emask;
}

bool is_valid_core(int mask, int rc, int p, int delta){
    if (rc == 0 or rc == 4) return true;
    bool LT = mask & (1 << (p - delta));
    bool RB = mask & (1 << (p + delta));
    return not(LT xor RB);
}

bool is_valid(int mask, int p){
    if (mask & (1 << p)) return false;
    int row = p / 5;
    int col = p % 5;
    return is_valid_core(mask, col, p, 1) and is_valid_core(mask, row, p, 5);
}

int main(){
    vector<int> pos(25, -1);  // pos[v] v番(0はじまり)がどの位置に配置済みであるか。未配置の場合は -1
    vector<int> zip(25, -1);  // zip[idx] idx 番目の位置(5*i+j)が、bit mask の下から何桁目に相当するか。座標の圧縮操作。
    vector<int> unzip;        // unzip[z] bit mask の下からz桁目は、どの位置(0-24)に該当するか。座標の復元操作。
    for (int idx = 0; idx != 25; ++idx){
        int v;
        cin >> v;
        if (v > 0){
            pos[v - 1] = idx;
        }else{
            zip[idx] = unzip.size();
            unzip.push_back(idx);
        }
    }
    int n = unzip.size();             // 未配置のマスの個数 = bit mask の桁数
    vector<long long> dp(1 << n, 0);  // dp[mask] mask のbitの立っている位置に、0からdp[mask].popcount() - 1 までを配置するパターン数
    dp[0] = 1;
    int used = 0;
    vector<int> pool = {0};           // pool: v-1 番まで配置したときの、mask のパターン
    for (int v = 0; v != 25; ++v){    // v: これから配置しようとしている番号
        vector<int> new_pool;
        if (pos[v] != -1){
            for (auto mask : pool){
                int emask = expand(mask, unzip);
                if (is_valid(emask|used, pos[v])){
                    new_pool.push_back(mask);
                }else{
                    dp[mask] = 0;
                }
            }
            used |= (1 << pos[v]);
        }else{
            for (auto mask : pool){
                int emask = expand(mask, unzip);
                for (auto p: unzip){
                    if (is_valid(emask|used, p)){
                        auto new_mask = mask | (1 << zip[p]);
                        if (dp[new_mask] == 0) new_pool.push_back(new_mask);
                        dp[new_mask] = (dp[new_mask] + dp[mask]) % mod;
                    }
                }
            }
        }
        swap(pool, new_pool);
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User rpy3cpp
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2867 Byte
Status AC
Exec Time 105 ms
Memory 9628 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 4
AC × 19
AC × 29
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Subtask1 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt
Subtask2 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, test-1-01.txt, test-1-02.txt, test-1-03.txt, test-1-04.txt, test-1-05.txt, test-1-06.txt, test-1-07.txt, test-1-08.txt, test-1-09.txt, test-1-10.txt, test-1-11.txt, test-1-12.txt, test-1-13.txt, test-1-14.txt, test-1-15.txt, test-2-01.txt, test-2-02.txt, test-2-03.txt, test-2-04.txt, test-2-05.txt, test-2-06.txt, test-2-07.txt, test-2-08.txt, test-2-09.txt, test-2-10.txt
Case Name Status Exec Time Memory
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sample-04.txt AC 1 ms 256 KB
test-1-01.txt AC 1 ms 256 KB
test-1-02.txt AC 1 ms 256 KB
test-1-03.txt AC 1 ms 256 KB
test-1-04.txt AC 1 ms 256 KB
test-1-05.txt AC 1 ms 256 KB
test-1-06.txt AC 1 ms 256 KB
test-1-07.txt AC 1 ms 256 KB
test-1-08.txt AC 1 ms 256 KB
test-1-09.txt AC 1 ms 256 KB
test-1-10.txt AC 1 ms 256 KB
test-1-11.txt AC 1 ms 256 KB
test-1-12.txt AC 1 ms 256 KB
test-1-13.txt AC 1 ms 256 KB
test-1-14.txt AC 1 ms 256 KB
test-1-15.txt AC 1 ms 256 KB
test-2-01.txt AC 2 ms 512 KB
test-2-02.txt AC 2 ms 384 KB
test-2-03.txt AC 1 ms 256 KB
test-2-04.txt AC 3 ms 768 KB
test-2-05.txt AC 7 ms 1408 KB
test-2-06.txt AC 72 ms 9224 KB
test-2-07.txt AC 43 ms 8808 KB
test-2-08.txt AC 65 ms 9100 KB
test-2-09.txt AC 57 ms 9184 KB
test-2-10.txt AC 105 ms 9628 KB