結果
問題 | No.12 限定された素数 |
ユーザー | koba-e964 |
提出日時 | 2015-07-07 14:33:30 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 211 ms / 5,000 ms |
コード長 | 2,820 bytes |
コンパイル時間 | 677 ms |
コンパイル使用メモリ | 70,460 KB |
実行使用メモリ | 88,448 KB |
最終ジャッジ日時 | 2024-05-03 09:28:14 |
合計ジャッジ時間 | 6,259 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 167 ms
88,320 KB |
testcase_01 | AC | 170 ms
88,448 KB |
testcase_02 | AC | 208 ms
88,192 KB |
testcase_03 | AC | 163 ms
88,136 KB |
testcase_04 | AC | 171 ms
88,236 KB |
testcase_05 | AC | 158 ms
88,192 KB |
testcase_06 | AC | 173 ms
88,252 KB |
testcase_07 | AC | 166 ms
88,152 KB |
testcase_08 | AC | 186 ms
88,240 KB |
testcase_09 | AC | 198 ms
88,320 KB |
testcase_10 | AC | 173 ms
88,296 KB |
testcase_11 | AC | 173 ms
88,320 KB |
testcase_12 | AC | 162 ms
88,192 KB |
testcase_13 | AC | 168 ms
88,100 KB |
testcase_14 | AC | 176 ms
88,316 KB |
testcase_15 | AC | 195 ms
88,140 KB |
testcase_16 | AC | 175 ms
88,192 KB |
testcase_17 | AC | 170 ms
88,132 KB |
testcase_18 | AC | 168 ms
88,268 KB |
testcase_19 | AC | 169 ms
88,320 KB |
testcase_20 | AC | 178 ms
88,192 KB |
testcase_21 | AC | 170 ms
88,320 KB |
testcase_22 | AC | 211 ms
88,192 KB |
testcase_23 | AC | 180 ms
88,192 KB |
testcase_24 | AC | 176 ms
88,136 KB |
testcase_25 | AC | 180 ms
88,192 KB |
ソースコード
#include <algorithm> #include <cmath> #include <iostream> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef vector<int> VI; /** * Segment Tree. This data structure is useful for fast folding on intervals of an array * whose elements are elements of monoid M. Note that constructing this tree requires the identity * element of M and the operation of M. * Header requirement: vector */ template<class I, class BiOp = I (*) (I, I)> class SegTree { int n; std::vector<I> dat; BiOp op; I e; public: SegTree(int n_, BiOp op, I e) : op(op), e(e) { n = 1; while (n < n_) { n *= 2; } // n is a power of 2 dat.resize(2 * n); for (int i = 0; i < 2 * n - 1; i++) { dat[i] = e; } } /* ary[k] <- v */ void update(int k, I v) { k += n - 1; dat[k] = v; while (k > 0) { k = (k - 1) / 2; dat[k] = op(dat[2 * k + 1], dat[2 * k + 2]); } } void update_array(int k, int len, const I *vals) { for (int i = 0; i < len; ++i) { update(k + i, vals[i]); } } /* Updates all elements. O(n) */ void update_all(const I *vals, int len) { for (int k = 0; k < min(n, len); ++k) { dat[k + n - 1] = vals[k]; } for (int k = min(n, len); k < n; ++k) { dat[k + n - 1] = e; } for (int b = n / 2; b >= 1; b /= 2) { for (int k = 0; k < b; ++k) { dat[k + b - 1] = op(dat[k * 2 + b * 2 - 1], dat[k * 2 + b * 2]); } } } /* l,r are for simplicity */ I querySub(int a, int b, int k, int l, int r) const { // [a,b) and [l,r) intersects? if (r <= a || b <= l) return e; if (a <= l && r <= b) return dat[k]; I vl = querySub(a, b, 2 * k + 1, l, (l + r) / 2); I vr = querySub(a, b, 2 * k + 2, (l + r) / 2, r); return op(vl, vr); } /* [a, b] (note: inclusive) */ I query(int a, int b) const { return querySub(a, b + 1, 0, 0, n); } }; const int N = 5000001; int tbl[N]; int dset(int v) { int bits = 0; while (v > 0) { bits |= 1 << (v % 10); v /= 10; } return bits; } struct bor { int operator()(int a, int b) const { return a | b; } }; void solve(int bits) { tbl[0] = tbl[1] = 0; REP(i, 2, N) { tbl[i] = dset(i); } REP(i, 2, sqrt(N) + 1) { if (tbl[i]) { REP(j, 2, (N + i - 1) / i) { tbl[i * j] = 0; } } } SegTree<int, bor> st(N, bor(), 0); st.update_all(tbl, N); int ma = -1; REP(i, 1, N) { int acc = 0; int j = i; for (; j < N; ++j) { if (tbl[j] & ~bits) { break; } acc |= tbl[j]; if (acc == bits) { ma = max(ma, j - i); } } i = j; } cout << ma << endl; } int main(void){ int sn; cin >> sn; int bits = 0; REP(i, 0, sn) { int y; cin >> y; bits |= 1 << y; } solve(bits); }