結果
問題 | No.12 限定された素数 |
ユーザー | tu-sa |
提出日時 | 2018-06-16 09:30:01 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 47 ms / 5,000 ms |
コード長 | 4,738 bytes |
コンパイル時間 | 1,253 ms |
コンパイル使用メモリ | 128,172 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-11-24 10:04:17 |
合計ジャッジ時間 | 3,157 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 46 ms
12,092 KB |
testcase_01 | AC | 44 ms
12,160 KB |
testcase_02 | AC | 43 ms
12,032 KB |
testcase_03 | AC | 46 ms
12,160 KB |
testcase_04 | AC | 45 ms
12,092 KB |
testcase_05 | AC | 45 ms
12,016 KB |
testcase_06 | AC | 44 ms
12,032 KB |
testcase_07 | AC | 45 ms
12,032 KB |
testcase_08 | AC | 44 ms
12,080 KB |
testcase_09 | AC | 45 ms
12,100 KB |
testcase_10 | AC | 47 ms
12,032 KB |
testcase_11 | AC | 47 ms
12,016 KB |
testcase_12 | AC | 46 ms
12,032 KB |
testcase_13 | AC | 43 ms
12,160 KB |
testcase_14 | AC | 44 ms
12,032 KB |
testcase_15 | AC | 46 ms
12,160 KB |
testcase_16 | AC | 46 ms
12,052 KB |
testcase_17 | AC | 44 ms
12,160 KB |
testcase_18 | AC | 44 ms
12,288 KB |
testcase_19 | AC | 46 ms
12,028 KB |
testcase_20 | AC | 44 ms
12,160 KB |
testcase_21 | AC | 45 ms
12,032 KB |
testcase_22 | AC | 46 ms
12,032 KB |
testcase_23 | AC | 45 ms
12,160 KB |
testcase_24 | AC | 45 ms
12,160 KB |
testcase_25 | AC | 45 ms
12,032 KB |
ソースコード
//////////////////////////////////////// /// tu3 pro-con template /// //////////////////////////////////////// #include <cassert> #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <sstream> #include <algorithm> #include <numeric> #include <functional> #include <vector> #include <queue> #include <string> #include <complex> #include <stack> #include <set> #include <map> #include <list> #include <unordered_map> #include <unordered_set> #include <bitset> #include <regex> #include <type_traits> #include <mutex> using namespace std; //// MACRO //// #define countof(a) (sizeof(a)/sizeof(a[0])) #define REP(i,n) for (int i = 0; i < (n); i++) #define RREP(i,n) for (int i = (n)-1; i >= 0; i--) #define FOR(i,s,n) for (int i = (s); i < (n); i++) #define RFOR(i,s,n) for (int i = (n)-1; i >= (s); i--) #define pos(c,i) c.being() + (i) #define allof(c) c.begin(), c.end() #define aallof(a) a, countof(a) #define partof(c,i,n) c.begin() + (i), c.begin() + (i) + (n) #define apartof(a,i,n) a + (i), a + (i) + (n) #define long long long #define EPS 1e-9 #define INF (1L << 30) #define LINF (1LL << 60) #define PREDICATE(t,a,exp) [&](const t & a) -> bool { return exp; } #define COMPARISON_T(t) bool(*)(const t &, const t &) #define COMPARISON(t,a,b,exp) [&](const t & a, const t & b) -> bool { return exp; } #define CONVERTER(TSrc,t,TDest,exp) [&](const TSrc &t)->TDest { return exp; } //// i/o helper //// template <class T> struct vevector : public vector<vector<T>> { vevector(int n = 0, int m = 0, const T &initial = T()) : vector<vector<T>>(n, vector<T>(m, initial)) { } }; template <class T> struct vevevector : public vector<vevector<T>> { vevevector(int n = 0, int m = 0, int l = 0, const T &initial = T()) : vector<vevector<T>>(n, vevector<T>(m, l, initial)) { } }; template <class T> struct vevevevector : public vector<vevevector<T>> { vevevevector(int n = 0, int m = 0, int l = 0, int k = 0, const T &initial = T()) : vector<vevevector<T>>(n, vevevector<T>(m, l, k, initial)) { } }; template <class T> T read() { T t; cin >> t; return t; } template <class T> vector<T> read(int n) { vector<T> v; v.reserve(n); REP(i, n) { v.push_back(read<T>()); } return v; } template <class T> vevector<T> read(int n, int m) { vevector<T> v; v.reserve(n); REP(i, n) v.push_back(read<T>(m)); return v; } template <class T> vector<T> readjag() { return read<T>(read<int>()); } template <class T> vevector<T> readjag(int n) { vevector<T> v; REP(i, n) v.push_back(readjag<T>()); return v; } template <class T1, class T2> inline istream & operator >> (istream & in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; } template <class T1, class T2> inline ostream & operator << (ostream &out, pair<T1, T2> &p) { out << p.first << p.second; return out; } template <class T> inline ostream & operator << (ostream &out, const vector<T> &v) { ostringstream ss; for (auto x : v) ss << x << ' '; auto s = ss.str(); out << s.substr(0, s.length() - 1); return out; } struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } }; struct _Writer { bool f; _Writer() : f(false) { } template <class T> _Writer operator ,(const T &rhs) { cout << (f ? " " : "") << rhs; f = true; return *this; } }; #define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__ #define WRITE(...) _Writer(), __VA_ARGS__; cout << '\n' void solve(); int main() { cin.tie(0); ios_base::sync_with_stdio(false); solve(); return 0; } // エラトステネス vector<unsigned char> isPrime; vector<int> primes; void initPrimes(int n) { isPrime = vector<unsigned char>(n + 1, true); primes.reserve(max(n / 10, 10000)); isPrime[0] = isPrime[1] = false; FOR(i, 2, n + 1) { if (!isPrime[i]) continue; primes.push_back(i); for (int j = i * 2; j <= n; j += i) isPrime[j] = false; } } inline int digitMask(int n) { int x = 0; while (n) { x |= 1 << n % 10; n /= 10; } return x; } //////////////////// /// template end /// //////////////////// void solve() { auto A = readjag<int>(); int mask = 0; for (auto x : A) { mask |= 1 << x; } initPrimes(5000000); vector<int> a; a.reserve(primes.size()); REP(i, primes.size()) { a.push_back(digitMask(primes[i])); } a.push_back(-1); int maxDiff = -1; REP (l, a.size()) { if ((a[l] | mask) == mask) { int curMask = 0; FOR (r, l, a.size()) { if ((a[r] | mask) == mask) { curMask |= a[r]; } else { if (curMask == mask) { int kk = l > 0 ? primes[l - 1] + 1 : 1; int ll = r < primes.size() ? primes[r] - 1 : 5000000; if (ll - kk > maxDiff) { maxDiff = ll - kk; } } l = r; break; } } } } WRITE(maxDiff); }