QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229541#7639. Forbidden Setucup-team228#AC ✓56ms13480kbC++202.0kb2023-10-28 16:23:562023-10-28 16:23:56

Judging History

This is the latest submission verdict.

  • [2023-10-28 16:23:56]
  • Judged
  • Verdict: AC
  • Time: 56ms
  • Memory: 13480kb
Show
  • [2023-10-28 16:23:56]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int C = 1e7 + 10;
bool prime[C];

void find_primes() {
    for (int i = 0; i <= C - 1; i++) {
        prime[i] = true;
    }
    prime[0] = prime[1] = false;
    for (int i = 2; i <= C - 1; i++) {
        if (prime[i]) {
            if (i * 1ll * i <= C - 1) {
                for (int j = i * i; j <= C - 1; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
}

const int inf = 1e9 + 10;
const int N = 10;
int ans[(1 << N)];

int int_to_mask(int x) {
    int mask = 0;
    while (x > 0) {
        mask |= (1 << (x % 10));
        x /= 10;
    }
    return mask;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    find_primes();
    for (int i = 0; i < (1 << N); i++) {
        ans[i] = inf;
    }
    for (int p = 2; p <= C - 1; p++) {
        if (prime[p]) {
            int mask = int_to_mask(p);
            ans[mask] = min(ans[mask], p);
        }
    }

//    for (int i = 0; i < (1 << N); i++) {
//        for (int j = 0; j < i; j++) {
//            if ((i & j) == j) {
//                ans[i] = min(ans[i], ans[j]);
//            }
//        }
//    }
//    for (int i = 0; i < (1 << N); i++) {
//        if (ans[i] == inf) {
//            cout << bitset<N>(i) << "\n";
//        }
//    }

    int k;
    cin >> k;
    int ban = 0;
    for (int i = 1; i <= k; i++) {
        int d;
        cin >> d;
        ban |= (1 << d);
    }
    int res = inf;
    for (int i = 0; i < (1 << N); i++) {
        if (ans[i] != inf && (i & ban) == 0) {
            res = min(res, ans[i]);
        }
    }
    if (res == inf) {
        cout << "-1\n";
    } else {
        cout << res << "\n";
    }

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 55ms
memory: 13344kb

input:

7
0
1
2
4
6
8
9

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 55ms
memory: 13412kb

input:

9
0
1
2
3
5
6
7
8
9

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 51ms
memory: 13476kb

input:

9
0
2
3
4
5
6
7
8
9

output:

11

result:

ok 1 number(s): "11"

Test #4:

score: 0
Accepted
time: 56ms
memory: 13372kb

input:

9
0
1
3
4
5
6
7
8
9

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 55ms
memory: 13372kb

input:

9
0
1
2
4
5
6
7
8
9

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 51ms
memory: 13336kb

input:

9
0
1
2
3
4
6
7
8
9

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 52ms
memory: 13380kb

input:

9
0
1
2
3
4
5
7
8
9

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 51ms
memory: 13452kb

input:

9
0
1
2
3
4
5
6
8
9

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: 0
Accepted
time: 55ms
memory: 13380kb

input:

9
0
1
2
3
4
5
6
7
9

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

score: 0
Accepted
time: 55ms
memory: 13372kb

input:

9
0
1
2
3
4
5
6
7
8

output:

-1

result:

ok 1 number(s): "-1"

Test #11:

score: 0
Accepted
time: 51ms
memory: 13320kb

input:

4
1
3
7
9

output:

2

result:

ok 1 number(s): "2"

Test #12:

score: 0
Accepted
time: 55ms
memory: 13376kb

input:

7
1
2
3
4
5
7
8

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

score: 0
Accepted
time: 56ms
memory: 13312kb

input:

8
0
1
2
3
4
5
7
8

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

score: 0
Accepted
time: 51ms
memory: 13416kb

input:

8
1
2
3
4
5
6
7
8

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

score: 0
Accepted
time: 55ms
memory: 13308kb

input:

5
1
2
3
5
7

output:

89

result:

ok 1 number(s): "89"

Test #16:

score: 0
Accepted
time: 52ms
memory: 13312kb

input:

6
1
2
3
5
7
8

output:

409

result:

ok 1 number(s): "409"

Test #17:

score: 0
Accepted
time: 52ms
memory: 13388kb

input:

8
0
1
2
3
5
6
7
8

output:

449

result:

ok 1 number(s): "449"

Test #18:

score: 0
Accepted
time: 55ms
memory: 13368kb

input:

5
2
3
5
7
9

output:

11

result:

ok 1 number(s): "11"

Test #19:

score: 0
Accepted
time: 51ms
memory: 13416kb

input:

6
1
2
4
5
7
8

output:

3

result:

ok 1 number(s): "3"

Test #20:

score: 0
Accepted
time: 50ms
memory: 13400kb

input:

8
0
1
2
4
5
7
8
9

output:

3

result:

ok 1 number(s): "3"

Test #21:

score: 0
Accepted
time: 52ms
memory: 13416kb

input:

8
0
1
3
5
6
7
8
9

output:

2

result:

ok 1 number(s): "2"

Test #22:

score: 0
Accepted
time: 56ms
memory: 13372kb

input:

8
0
2
3
5
6
7
8
9

output:

11

result:

ok 1 number(s): "11"

Test #23:

score: 0
Accepted
time: 51ms
memory: 13476kb

input:

8
0
2
4
5
6
7
8
9

output:

3

result:

ok 1 number(s): "3"

Test #24:

score: 0
Accepted
time: 55ms
memory: 13312kb

input:

7
0
2
3
5
6
7
8

output:

11

result:

ok 1 number(s): "11"

Test #25:

score: 0
Accepted
time: 55ms
memory: 13404kb

input:

8
2
3
4
5
6
7
8
9

output:

11

result:

ok 1 number(s): "11"

Test #26:

score: 0
Accepted
time: 55ms
memory: 13368kb

input:

8
0
1
2
5
6
7
8
9

output:

3

result:

ok 1 number(s): "3"

Test #27:

score: 0
Accepted
time: 55ms
memory: 13416kb

input:

1
2

output:

3

result:

ok 1 number(s): "3"

Test #28:

score: 0
Accepted
time: 51ms
memory: 13320kb

input:

10
0
1
2
3
4
5
6
7
8
9

output:

-1

result:

ok 1 number(s): "-1"

Test #29:

score: 0
Accepted
time: 52ms
memory: 13384kb

input:

7
0
2
3
5
6
8
9

output:

7

result:

ok 1 number(s): "7"

Test #30:

score: 0
Accepted
time: 52ms
memory: 13452kb

input:

8
1
2
3
4
5
6
7
9

output:

-1

result:

ok 1 number(s): "-1"

Test #31:

score: 0
Accepted
time: 55ms
memory: 13408kb

input:

4
0
2
6
7

output:

3

result:

ok 1 number(s): "3"

Test #32:

score: 0
Accepted
time: 51ms
memory: 13408kb

input:

5
2
3
4
6
8

output:

5

result:

ok 1 number(s): "5"

Test #33:

score: 0
Accepted
time: 48ms
memory: 13404kb

input:

6
0
2
3
4
5
8

output:

7

result:

ok 1 number(s): "7"

Test #34:

score: 0
Accepted
time: 54ms
memory: 13376kb

input:

3
1
5
7

output:

2

result:

ok 1 number(s): "2"

Test #35:

score: 0
Accepted
time: 50ms
memory: 13480kb

input:

3
1
4
9

output:

2

result:

ok 1 number(s): "2"

Test #36:

score: 0
Accepted
time: 51ms
memory: 13388kb

input:

6
2
3
4
6
7
9

output:

5

result:

ok 1 number(s): "5"

Test #37:

score: 0
Accepted
time: 50ms
memory: 13388kb

input:

7
1
2
3
4
5
6
8

output:

7

result:

ok 1 number(s): "7"

Test #38:

score: 0
Accepted
time: 52ms
memory: 13384kb

input:

6
0
1
3
5
8
9

output:

2

result:

ok 1 number(s): "2"

Test #39:

score: 0
Accepted
time: 52ms
memory: 13416kb

input:

3
1
3
4

output:

2

result:

ok 1 number(s): "2"

Test #40:

score: 0
Accepted
time: 55ms
memory: 13364kb

input:

4
1
5
6
9

output:

2

result:

ok 1 number(s): "2"

Test #41:

score: 0
Accepted
time: 55ms
memory: 13384kb

input:

7
0
2
3
5
6
7
9

output:

11

result:

ok 1 number(s): "11"

Test #42:

score: 0
Accepted
time: 50ms
memory: 13420kb

input:

4
0
3
7
9

output:

2

result:

ok 1 number(s): "2"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-09 03:59:12 | OpenSource Project