编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#4765 #1025. 质数迷宫 Time Limit Exceeded 0 14045 ms 388 K C++ 17 / 2.2 K hymonade 2024-01-17 16:58:59
显示原始代码
#include <bits/stdc++.h>
using namespace std;
int a[5][5];
int s[12], num[12];
bool out = false;
bool isprime(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0)
            return false;
    }
    return true;
}
void dfs(int pos) {
    // cout << pos << " ";
    if (pos == 25) {
        out = true;
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                printf("%d", a[i][j]);
            }
            printf("\n");
        }
        return;
    }
    int r = pos / 4, c = pos % 4;
    if (r == 4) {
        if (s[c + 5] >= 10 || s[c + 5] & 1 == 0 || s[c + 5] == 5)
            return;
        a[r][c] = s[c + 5];
        if (c == 0) {
            if (s[10] - a[r][c] != 0)
                return;
            num[10] = 0;
            for (int i = 0; i < 5; ++i) num[10] = num[10] * 10 + a[4 - i][i];
            if (!isprime(num[10]))
                return;
        } else if (c == 4) {
            if (s[11] - a[r][c] != 0)
                return;
            num[11] = 0;
            for (int i = 0; i < 5; ++i) num[11] = num[11] * 10 + a[i][i];
            if (!isprime(num[11]))
                return;
        }
        num[c + 5] = 0;
        for (int i = 0; i < 5; ++i) num[c + 5] = num[c + 5] * 10 + a[i][c];
        if (!isprime(num[c + 5]))
            return;
        dfs(pos + 1);
    } else if (c == 4) {
        if (s[r] >= 10 || s[r] & 1 == 0 || s[r] == 5)
            return;
        a[r][c] = s[r];
        num[r] = 0;
        for (int i = 0; i < 5; ++i) num[r] = num[r] * 10 + a[r][i];
        if (!isprime(num[r]))
            return;
        dfs(pos + 1);
    } else {
        int minn = 10;
        minn = min(10, min(min(s[10], s[11]), min(s[r], s[c + 5])));
        // cout << minn << "\n";
        if (c == 0 xor r == 0) {
            for (int i = 1; i < minn; ++i) {
                a[r][c] = i;
                s[r] -= i;
                s[c + 5] -= i;
                if (r == c) {
                    s[11] -= i;
                }
                if (r + c == 4) {
                    s[10] -= i;
                }
                dfs(pos + 1);
                if (r == c) {
                    s[11] += i;
                }
                if (r + c == 4) {
                    s[10] += i;
                }
                s[r] += i;
                s[c + 5] += i;
            }
        } else {
            for (int i = 0; i < minn; ++i) {
                a[r][c] = i;
                s[r] -= i;
                s[c + 5] -= i;
                if (r == c) {
                    s[11] -= i;
                }
                if (r + c == 4) {
                    s[10] -= i;
                }
                dfs(pos + 1);
                if (r == c) {
                    s[11] += i;
                }
                if (r + c == 4) {
                    s[10] += i;
                }
                s[r] += i;
                s[c + 5] += i;
            }
        }
    }
    return;
}
int main() {
    int sum;
    scanf("%d %d", &sum, &a[1][1]);
    for (int i = 0; i < 12; ++i) s[i] = sum;
    dfs(1);
    if (out == false)
        printf("NONE");
    return 0;
}
子任务 #1
Time Limit Exceeded
得分:0
测试点 #1
Time Limit Exceeded
得分:0
用时:2008 ms
内存:236 KiB

输入文件(prime31.in

11 2

答案文件(prime31.out

25121
10271
54101
21611
11117
测试点 #2
Time Limit Exceeded
得分:0
用时:2006 ms
内存:388 KiB

输入文件(prime33.in

17 7

答案文件(prime33.out

71153
13553
15137
55331
33713

72431
42227
24533
38303
11393

73331
32327
33533
38303
<46 bytes omitted>
测试点 #3
Time Limit Exceeded
得分:0
用时:2003 ms
内存:384 KiB

输入文件(prime34.in

29 2

答案文件(prime34.out

23879
48953
95267
76781
77339

23879
76943
47387
74891
99119

24977
38567
89273
75683
<638 bytes omitted>
测试点 #4
Time Limit Exceeded
得分:0
用时:2004 ms
内存:380 KiB

输入文件(prime36.in

17 1

答案文件(prime36.out

11159
48221
82223
33353
13931

11393
24137
43613
72431
37313

11393
42821
86201
17333
<1785 bytes omitted>
测试点 #5
Time Limit Exceeded
得分:0
用时:2013 ms
内存:380 KiB

输入文件(prime38.in

23 7

答案文件(prime38.out

71249
29741
95027
27743
31793

71249
55661
66533
42737
19373

71249
55661
86531
22739
<5374 bytes omitted>
测试点 #6
Time Limit Exceeded
得分:0
用时:2004 ms
内存:352 KiB

输入文件(prime39.in

23 1

答案文件(prime39.out

11399
75821
63671
85523
19139

11399
94811
63671
66533
19139

11939
61961
69431
93083
<3154 bytes omitted>
测试点 #7
Time Limit Exceeded
得分:0
用时:2007 ms
内存:384 KiB

输入文件(prime310.in

23 3

答案文件(prime310.out

31379
58109
53951
72923
39191

31649
48371
93407
62753
19373

31649
86441
63527
54563
<5522 bytes omitted>