Submission #1607993


Source Code Expand

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
#define MOD 1000000007

int dp[1<<25];

bool isOK(int i, int z){
    if(i & (1<<z)) return false;
    int y = z / 5;
    int x = z % 5;
    if(0 < x && x < 4){
        int z1 = z-1;
        int z2 = z+1;
        if( ((i>>z1)^(i>>z2))&1 ) return false;
    }
    if(0 < y && y < 4){
        int z3 = z-5;
        int z4 = z+5;
        if( ((i>>z3)^(i>>z4))&1 ) return false;
    }
    return true;
}

int main(){
    int x[5][5];
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            cin >> x[i][j];
    vector<int> emp;
    int occ[25];
    fill_n(occ, 25, -1);
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            if(x[i][j] != 0) occ[x[i][j]-1] = 5*i+j;
            else emp.push_back(5*i+j);

    fill_n(dp, 1<<25, 0);
    dp[0] = 1;
    for(int i=0; i<(1<<25)-1; i++){
        if(dp[i] == 0) continue;
        int num = bitset<25>(i).count();
        if(occ[num] != -1){
            int z = occ[num];
            if(isOK(i, z)){
                dp[i + (1<<z)] += dp[i];
                dp[i + (1<<z)] %= MOD;
            }
        }else{
            for(int z : emp)
                if(isOK(i, z)){
                    dp[i + (1<<z)] += dp[i];
                    dp[i + (1<<z)] %= MOD;
                }
        }
    }
    cout << dp[(1<<25)-1] << endl;

    return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User suzume
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1446 Byte
Status AC
Exec Time 117 ms
Memory 131328 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 62 ms 131328 KB
sample-02.txt AC 62 ms 131328 KB
sample-03.txt AC 62 ms 131328 KB
sample-04.txt AC 62 ms 131328 KB
test-1-01.txt AC 62 ms 131328 KB
test-1-02.txt AC 62 ms 131328 KB
test-1-03.txt AC 62 ms 131328 KB
test-1-04.txt AC 62 ms 131328 KB
test-1-05.txt AC 62 ms 131328 KB
test-1-06.txt AC 62 ms 131328 KB
test-1-07.txt AC 62 ms 131328 KB
test-1-08.txt AC 62 ms 131328 KB
test-1-09.txt AC 62 ms 131328 KB
test-1-10.txt AC 62 ms 131328 KB
test-1-11.txt AC 62 ms 131328 KB
test-1-12.txt AC 62 ms 131328 KB
test-1-13.txt AC 62 ms 131328 KB
test-1-14.txt AC 62 ms 131328 KB
test-1-15.txt AC 62 ms 131328 KB
test-2-01.txt AC 62 ms 131328 KB
test-2-02.txt AC 62 ms 131328 KB
test-2-03.txt AC 62 ms 131328 KB
test-2-04.txt AC 63 ms 131328 KB
test-2-05.txt AC 66 ms 131328 KB
test-2-06.txt AC 99 ms 131328 KB
test-2-07.txt AC 85 ms 131328 KB
test-2-08.txt AC 96 ms 131328 KB
test-2-09.txt AC 91 ms 131328 KB
test-2-10.txt AC 117 ms 131328 KB