結果
問題 | No.12 限定された素数 |
ユーザー | togari_takamoto |
提出日時 | 2015-12-13 20:54:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 151 ms / 5,000 ms |
コード長 | 1,700 bytes |
コンパイル時間 | 869 ms |
コンパイル使用メモリ | 95,568 KB |
実行使用メモリ | 27,264 KB |
最終ジャッジ日時 | 2023-08-15 23:10:17 |
合計ジャッジ時間 | 5,787 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 139 ms
25,592 KB |
testcase_01 | AC | 149 ms
27,264 KB |
testcase_02 | AC | 144 ms
25,908 KB |
testcase_03 | AC | 129 ms
25,924 KB |
testcase_04 | AC | 149 ms
25,472 KB |
testcase_05 | AC | 142 ms
25,400 KB |
testcase_06 | AC | 151 ms
26,204 KB |
testcase_07 | AC | 138 ms
26,936 KB |
testcase_08 | AC | 142 ms
25,600 KB |
testcase_09 | AC | 139 ms
26,672 KB |
testcase_10 | AC | 136 ms
26,448 KB |
testcase_11 | AC | 140 ms
25,612 KB |
testcase_12 | AC | 138 ms
25,736 KB |
testcase_13 | AC | 141 ms
26,400 KB |
testcase_14 | AC | 135 ms
27,184 KB |
testcase_15 | AC | 139 ms
26,784 KB |
testcase_16 | AC | 142 ms
25,728 KB |
testcase_17 | AC | 143 ms
25,944 KB |
testcase_18 | AC | 139 ms
25,936 KB |
testcase_19 | AC | 137 ms
26,408 KB |
testcase_20 | AC | 134 ms
25,988 KB |
testcase_21 | AC | 133 ms
25,396 KB |
testcase_22 | AC | 137 ms
25,616 KB |
testcase_23 | AC | 145 ms
26,524 KB |
testcase_24 | AC | 139 ms
25,920 KB |
testcase_25 | AC | 150 ms
26,656 KB |
ソースコード
#include <iostream> #include <vector> #include <array> #include <algorithm> #include <string> #include <map> #include <queue> #include <iomanip> #include <numeric> #include <memory> #include <limits.h> #include <set> #include <cassert> #include <cmath> #include <bitset> #include <functional> #include <limits> using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i,n) for(ll i=0; i<(n); ++i) #define TEN(x) ((ll)1e##x) #define ALL(v) (v).begin(), (v).end() // エラトステネスのふるい O(n log log n) : t[i] = true ⇔ iが素数 (i <= n) vector<int> sieve_of_eratosthenes(ll n) { vector<int> t(n+1, true); t[0] = t[1] = false; for(ll i = 2; i <= n; ++i) if (t[i]){ for(ll j = 2*i; j <= n; j += i) t[j] = false; } return t; } vector<ll> get_occur_list(ll x) { vector<ll> occur(10, 0); while (x!=0) { occur[x % 10]++; x /= 10; } return occur; } int main(){ vector<bool> a(10, false); ll n; cin >> n; REP(_, n) { ll i; cin >> i; a[i] = true; } vector<ll> p; p.reserve(5000000); { auto t = sieve_of_eratosthenes(5000000); REP(i, t.size()) if (t[i]) p.push_back(i); } ll max_interval = -1; vector<ll> occur(10, 0); ll end = -1; REP(i, p.size()) { auto _ = get_occur_list(p[i]); REP(j, 10) occur[j] += _[j]; REP(j, 10) if(!a[j]) while(occur[j]!=0){ end++; auto _ = get_occur_list(p[end]); REP(k, 10) occur[k] -= _[k]; } bool valid = true; REP(j, 10) if (a[j]) if (occur[j] == 0) valid = false; if (valid) { ll k = (end == -1) ? 1 : p[end] + 1 ; ll l = (i == p.size() - 1) ? 5000000 : p[i+1] - 1 ; max_interval = max(max_interval, l - k); } } cout << max_interval << endl; return 0; }