結果
問題 | No.12 限定された素数 |
ユーザー | tottoripaper |
提出日時 | 2014-11-16 05:43:10 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 33 ms / 5,000 ms |
コード長 | 1,347 bytes |
コンパイル時間 | 527 ms |
コンパイル使用メモリ | 60,384 KB |
実行使用メモリ | 11,564 KB |
最終ジャッジ日時 | 2024-05-03 08:52:24 |
合計ジャッジ時間 | 1,980 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
11,432 KB |
testcase_01 | AC | 30 ms
11,312 KB |
testcase_02 | AC | 30 ms
11,440 KB |
testcase_03 | AC | 29 ms
11,564 KB |
testcase_04 | AC | 31 ms
11,436 KB |
testcase_05 | AC | 30 ms
11,436 KB |
testcase_06 | AC | 30 ms
11,432 KB |
testcase_07 | AC | 31 ms
11,436 KB |
testcase_08 | AC | 31 ms
11,564 KB |
testcase_09 | AC | 32 ms
11,436 KB |
testcase_10 | AC | 31 ms
11,308 KB |
testcase_11 | AC | 31 ms
11,432 KB |
testcase_12 | AC | 33 ms
11,564 KB |
testcase_13 | AC | 33 ms
11,312 KB |
testcase_14 | AC | 31 ms
11,436 KB |
testcase_15 | AC | 31 ms
11,440 KB |
testcase_16 | AC | 32 ms
11,376 KB |
testcase_17 | AC | 31 ms
11,436 KB |
testcase_18 | AC | 31 ms
11,436 KB |
testcase_19 | AC | 32 ms
11,308 KB |
testcase_20 | AC | 33 ms
11,440 KB |
testcase_21 | AC | 32 ms
11,436 KB |
testcase_22 | AC | 31 ms
11,440 KB |
testcase_23 | AC | 31 ms
11,560 KB |
testcase_24 | AC | 32 ms
11,436 KB |
testcase_25 | AC | 32 ms
11,440 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:38:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:40:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | REP(i, N){int a; scanf("%d", &a); restricted |= 1 << a;} | ~~~~~^~~~~~~~~~
ソースコード
#include <cstdio> #include <iostream> #include <vector> #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,j) FOR(i,0,j) typedef long long ll; std::vector<int> primes; bool isPrime[5000101]; int xs[348518]; int N, A[10]; int main(){ std::fill(isPrime, isPrime+5000101, true); std::fill(&xs[0], &xs[0]+348518, 0); primes.push_back(0); primes.push_back(2); xs[1] = 0x4; for(int i=4;i<=5000100;i+=2){isPrime[i] = false;} int length = 2; for(ll i=3;i<=5000100;i+=2){ if(isPrime[i]){ primes.push_back(i); int x = i; while(x > 0){xs[length] |= 1 << (x % 10); x /= 10;} length += 1; for(ll j=i*i;j<=5000100ll;j+=i){ isPrime[j] = false; } } } scanf("%d", &N); int restricted = 0; REP(i, N){int a; scanf("%d", &a); restricted |= 1 << a;} int res = -1; for(int i=1,j=1;i<348514;){ int y = 0; while(j < 348514 && (~restricted & xs[j]) == 0){ y |= xs[j]; j += 1; } if(y == restricted){ res = std::max(res, std::min(primes[j],5000001)-primes[i-1]-2); } i = j+1; j = i; } printf("%d\n", res); }