結果
問題 | No.12 限定された素数 |
ユーザー | myanta |
提出日時 | 2017-04-30 22:48:20 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 981 ms / 5,000 ms |
コード長 | 1,597 bytes |
コンパイル時間 | 336 ms |
コンパイル使用メモリ | 42,112 KB |
実行使用メモリ | 17,920 KB |
最終ジャッジ日時 | 2024-05-03 10:30:01 |
合計ジャッジ時間 | 27,224 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 971 ms
17,792 KB |
testcase_01 | AC | 969 ms
17,792 KB |
testcase_02 | AC | 966 ms
17,792 KB |
testcase_03 | AC | 952 ms
17,792 KB |
testcase_04 | AC | 956 ms
17,792 KB |
testcase_05 | AC | 965 ms
17,792 KB |
testcase_06 | AC | 977 ms
17,792 KB |
testcase_07 | AC | 976 ms
17,792 KB |
testcase_08 | AC | 968 ms
17,792 KB |
testcase_09 | AC | 981 ms
17,792 KB |
testcase_10 | AC | 974 ms
17,920 KB |
testcase_11 | AC | 956 ms
17,664 KB |
testcase_12 | AC | 948 ms
17,792 KB |
testcase_13 | AC | 977 ms
17,664 KB |
testcase_14 | AC | 966 ms
17,792 KB |
testcase_15 | AC | 958 ms
17,792 KB |
testcase_16 | AC | 960 ms
17,792 KB |
testcase_17 | AC | 958 ms
17,792 KB |
testcase_18 | AC | 964 ms
17,792 KB |
testcase_19 | AC | 948 ms
17,664 KB |
testcase_20 | AC | 973 ms
17,792 KB |
testcase_21 | AC | 968 ms
17,792 KB |
testcase_22 | AC | 972 ms
17,792 KB |
testcase_23 | AC | 961 ms
17,792 KB |
testcase_24 | AC | 959 ms
17,792 KB |
testcase_25 | AC | 974 ms
17,792 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:83:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 83 | scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include<cstdio> #include<vector> using namespace std; #define L_MAX 5000000 class prime_t { public: int x; int c[10]; prime_t(int x) { int i; for(i=0;i<10;i++) c[i]=0; this->x=x; for(;x;x/=10) { c[x%10]=1; } } }; vector<prime_t> prime; void init(void) { int i, j; prime.clear(); prime.reserve(L_MAX/4); prime.push_back(prime_t(0)); prime.push_back(prime_t(2)); for(i=3;i<=L_MAX;i+=2) { for(j=3;j*j<=i;j+=2) { if(i%j==0) break; } if(j*j>i) { prime.push_back(prime_t(i)); } } prime.push_back(prime_t(L_MAX+1)); } int max_u(int& m, int v) { if(m<v) { m=v; return 1; } return 0; } int main(void) { int n, i; vector<int> a, b, c, f; int ps, pe, max, d, k, l, ok, ng; init(); while(scanf("%d", &n)==1) { a.resize(n); f.clear(); f.resize(10); c.clear(); c.resize(10); for(i=0;i<n;i++) { scanf("%d", &a[i]); f[a[i]]=1; } ok=ng=0; max=-1; ps=1; for(pe=1;pe+1<prime.size();pe++) { for(i=0;i<10;i++) { d=prime[pe].c[i]; if(d==0) continue; if(c[i]==0) { if(f[i]) ok++; else ng++; } c[i]++; } if(ok==n) { for(;ps<=pe;ps++) { if(ng==0) break; for(i=0;i<10;i++) { d=prime[ps].c[i]; if(d==0) continue; c[i]--; if(c[i]==0) { if(f[i]) ok--; else ng--; } } } } if(ok==n && ng==0) { k=prime[ps-1].x+1; l=prime[pe+1].x-1; if(max_u(max, l-k)) { // printf("l=%d k=%d max=%d\n", l, k, max); } } } printf("%d\n", max); } return 0; }