結果
問題 |
No.12 限定された素数
|
ユーザー |
![]() |
提出日時 | 2018-11-02 22:01:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 200 ms / 5,000 ms |
コード長 | 1,990 bytes |
コンパイル時間 | 1,899 ms |
コンパイル使用メモリ | 204,648 KB |
最終ジャッジ日時 | 2025-01-06 15:27:33 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; using vi = vector<i64>; using vvi = vector<vi>; const int nax = 5000001; vi ps; int main() { ps = vi(nax, 1); ps[0] = ps[1] = 0; for (int i = 2; i < nax; i++) { if (!ps[i]) continue; for (int j = 2; i * j < nax; j++) { ps[i * j] = 0; } } vi qs; for (int i = 0; i < nax; i++) { if (ps[i]) qs.push_back(i); } int n; cin >> n; set<int> use; for (int i = 0; i < n; i++) { int a; cin >> a; use.insert(a); } set<int> ss; int l = 0, r = 0; i64 width = -1; while (1) { if (use != ss) { if (r == qs.size()) break; int q = qs[r]; int ok = 1; while (q) { if (use.count(q % 10) == 0) { ok = 0; } q /= 10; } if (ok) { q = qs[r]; while (q) { ss.insert(q % 10); q /= 10; } if (use == ss) { width = max(width, ((r + 1 == qs.size() ? nax : qs[r + 1]) - 1) - ((l == 0 ? 0 : qs[l - 1]) + 1)); } r++; } else { l = r + 1; r = l; ss.clear(); } } else { if (r == qs.size()) break; int q = qs[r]; int ok = 1; while (q) { if (use.count(q % 10) == 0) { ok = 0; } q /= 10; } if (ok) { width = max(width, ((r + 1 == qs.size() ? nax : qs[r + 1]) - 1) - ((l == 0 ? 0 : qs[l - 1]) + 1)); r++; } else { l = r + 1; r = l; ss.clear(); } } } cout << width << endl; }