Submission #1493863


Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
using llng = long long;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T> >;

const int MOD = 1e9+7;
int x[5][5];
v<bool> used(26, false);

bool valid(int p) {
    int i = p/5, j = p%5;
    if (2 <= i) {
        if (x[i-2][j] < x[i-1][j] && x[i-1][j] < x[i][j]) return false;
        if (x[i-2][j] > x[i-1][j] && x[i-1][j] > x[i][j]) return false;
    }
    if (2 <= j) {
        if (x[i][j-2] < x[i][j-1] && x[i][j-1] < x[i][j]) return false;
        if (x[i][j-2] > x[i][j-1] && x[i][j-1] > x[i][j]) return false;
    }
    return true;
}

int dfs(int p) {
    if (p == 25) return 1;

    int i = p/5, j = p%5;

    if (x[i][j] != 0) {
        if (!valid(p)) return 0;
        else return dfs(p+1);
    }
    int ret = 0;
    for (int k=1; k<=25; k++) if (!used[k]) {
        used[k] = true;
        x[i][j] = k;
        (ret += dfs(p+1)) %= MOD;
        x[i][j] = 0;
        used[k] = false;
    }
    return ret;
}

int main() {
    for (int i=0; i<5; i++) for (int j=0; j<5; j++) {
        cin >> x[i][j]; used[x[i][j]] = true;
    }

    cout << dfs(0) << endl;

    return 0;
}

Submission Info

Submission Time
Task D - 25個の整数
User hidollara
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1272 Byte
Status WA
Exec Time 5255 ms
Memory 256 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 4
AC × 10
WA × 9
AC × 10
WA × 10
TLE × 9
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 4 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 WA 1 ms 256 KB
test-1-03.txt WA 1 ms 256 KB
test-1-04.txt WA 1 ms 256 KB
test-1-05.txt WA 1 ms 256 KB
test-1-06.txt WA 2 ms 256 KB
test-1-07.txt AC 1 ms 256 KB
test-1-08.txt WA 2 ms 256 KB
test-1-09.txt WA 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 WA 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 WA 1 ms 256 KB
test-2-01.txt TLE 5255 ms 256 KB
test-2-02.txt TLE 5255 ms 256 KB
test-2-03.txt WA 2720 ms 256 KB
test-2-04.txt TLE 5255 ms 256 KB
test-2-05.txt TLE 5255 ms 256 KB
test-2-06.txt TLE 5255 ms 256 KB
test-2-07.txt TLE 5255 ms 256 KB
test-2-08.txt TLE 5255 ms 256 KB
test-2-09.txt TLE 5255 ms 256 KB
test-2-10.txt TLE 5255 ms 256 KB