結果
問題 | No.12 限定された素数 |
ユーザー | NotationNap |
提出日時 | 2015-04-23 01:51:05 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 91 ms / 5,000 ms |
コード長 | 1,384 bytes |
コンパイル時間 | 1,525 ms |
コンパイル使用メモリ | 163,064 KB |
実行使用メモリ | 10,200 KB |
最終ジャッジ日時 | 2024-05-03 09:22:42 |
合計ジャッジ時間 | 4,550 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 86 ms
10,072 KB |
testcase_01 | AC | 86 ms
9,948 KB |
testcase_02 | AC | 86 ms
10,016 KB |
testcase_03 | AC | 73 ms
10,072 KB |
testcase_04 | AC | 87 ms
10,072 KB |
testcase_05 | AC | 87 ms
10,072 KB |
testcase_06 | AC | 86 ms
10,200 KB |
testcase_07 | AC | 87 ms
10,200 KB |
testcase_08 | AC | 85 ms
10,200 KB |
testcase_09 | AC | 87 ms
10,072 KB |
testcase_10 | AC | 87 ms
9,940 KB |
testcase_11 | AC | 83 ms
10,068 KB |
testcase_12 | AC | 85 ms
10,068 KB |
testcase_13 | AC | 87 ms
10,072 KB |
testcase_14 | AC | 86 ms
10,072 KB |
testcase_15 | AC | 86 ms
9,944 KB |
testcase_16 | AC | 91 ms
9,940 KB |
testcase_17 | AC | 86 ms
9,944 KB |
testcase_18 | AC | 86 ms
10,068 KB |
testcase_19 | AC | 86 ms
9,948 KB |
testcase_20 | AC | 86 ms
9,944 KB |
testcase_21 | AC | 87 ms
10,020 KB |
testcase_22 | AC | 86 ms
10,068 KB |
testcase_23 | AC | 86 ms
10,072 KB |
testcase_24 | AC | 87 ms
10,072 KB |
testcase_25 | AC | 87 ms
10,072 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long Int; #define REP(i,n) for(int (i)=0;(i)<(int)(n);++(i)) const int MAX_N = 5000000; bool is_prime[MAX_N]; vector<int> primes; vector<int> dis(int p) { vector<int> res(10); while (p > 0) { res[p % 10]++; p /= 10; } return res; } int main() { for (int i = 0; i < MAX_N; i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= MAX_N; i++) if (is_prime[i]) for (int j = i * i; j < MAX_N; j += i) is_prime[j] = false; primes.push_back(0); for (int i = 0; i < MAX_N; i++) { if (is_prime[i]) primes.push_back(i); } primes.push_back(5000001); vector<int> target(10); int N; cin >> N; REP(i, N) { int x; cin >> x; target[x]++; } vector<int> current(10); int left = 1, right = 1; int ans = -1; int LIM = primes.size() - 1; while (right < LIM || left < LIM) { bool fast = false; bool slow = false; REP(i, 10) { if (current[i] > 0 && target[i] == 0) fast = true; if (current[i] == 0 && target[i] > 0) slow = true; } if (!fast && !slow) { ans = max(ans, (primes[right] - 1) - (primes[left-1] + 1)); } if (right >= LIM || fast) { vector<int> v = dis(primes[left]); REP(i, 10) current[i] -= v[i]; left++; } else { vector<int> v = dis(primes[right]); REP(i, 10) current[i] += v[i]; right++; } } cout << ans << endl; }