結果
問題 | No.12 限定された素数 |
ユーザー |
|
提出日時 | 2015-04-23 01:51:05 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 89 ms / 5,000 ms |
コード長 | 1,384 bytes |
コンパイル時間 | 1,517 ms |
コンパイル使用メモリ | 162,020 KB |
実行使用メモリ | 10,200 KB |
最終ジャッジ日時 | 2024-11-24 08:07:21 |
合計ジャッジ時間 | 4,555 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#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; }