結果
問題 | No.12 限定された素数 |
ユーザー | togari_takamoto |
提出日時 | 2015-12-13 20:54:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 179 ms / 5,000 ms |
コード長 | 1,700 bytes |
コンパイル時間 | 921 ms |
コンパイル使用メモリ | 96,824 KB |
実行使用メモリ | 27,040 KB |
最終ジャッジ日時 | 2024-05-03 09:38:19 |
合計ジャッジ時間 | 6,229 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 165 ms
26,856 KB |
testcase_01 | AC | 169 ms
26,924 KB |
testcase_02 | AC | 177 ms
25,584 KB |
testcase_03 | AC | 160 ms
26,364 KB |
testcase_04 | AC | 166 ms
25,684 KB |
testcase_05 | AC | 165 ms
25,932 KB |
testcase_06 | AC | 175 ms
25,832 KB |
testcase_07 | AC | 179 ms
25,872 KB |
testcase_08 | AC | 172 ms
26,056 KB |
testcase_09 | AC | 162 ms
25,624 KB |
testcase_10 | AC | 176 ms
25,960 KB |
testcase_11 | AC | 176 ms
26,380 KB |
testcase_12 | AC | 167 ms
25,584 KB |
testcase_13 | AC | 160 ms
25,616 KB |
testcase_14 | AC | 167 ms
26,748 KB |
testcase_15 | AC | 152 ms
25,524 KB |
testcase_16 | AC | 153 ms
27,040 KB |
testcase_17 | AC | 166 ms
26,852 KB |
testcase_18 | AC | 160 ms
25,536 KB |
testcase_19 | AC | 170 ms
26,416 KB |
testcase_20 | AC | 173 ms
25,960 KB |
testcase_21 | AC | 172 ms
25,596 KB |
testcase_22 | AC | 170 ms
26,628 KB |
testcase_23 | AC | 174 ms
25,808 KB |
testcase_24 | AC | 171 ms
26,428 KB |
testcase_25 | AC | 170 ms
26,044 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; }