結果
問題 | No.12 限定された素数 |
ユーザー | kosakkun |
提出日時 | 2017-01-10 17:55:43 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 411 ms / 5,000 ms |
コード長 | 2,903 bytes |
コンパイル時間 | 1,082 ms |
コンパイル使用メモリ | 107,224 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-24 09:01:53 |
合計ジャッジ時間 | 5,199 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
6,820 KB |
testcase_01 | AC | 84 ms
6,820 KB |
testcase_02 | AC | 55 ms
6,820 KB |
testcase_03 | AC | 411 ms
6,816 KB |
testcase_04 | AC | 52 ms
6,820 KB |
testcase_05 | AC | 112 ms
6,816 KB |
testcase_06 | AC | 179 ms
6,816 KB |
testcase_07 | AC | 213 ms
6,820 KB |
testcase_08 | AC | 93 ms
6,816 KB |
testcase_09 | AC | 79 ms
6,820 KB |
testcase_10 | AC | 100 ms
6,820 KB |
testcase_11 | AC | 285 ms
6,816 KB |
testcase_12 | AC | 209 ms
6,820 KB |
testcase_13 | AC | 135 ms
6,816 KB |
testcase_14 | AC | 96 ms
6,816 KB |
testcase_15 | AC | 133 ms
6,820 KB |
testcase_16 | AC | 248 ms
6,816 KB |
testcase_17 | AC | 43 ms
6,816 KB |
testcase_18 | AC | 42 ms
6,820 KB |
testcase_19 | AC | 41 ms
6,816 KB |
testcase_20 | AC | 61 ms
6,816 KB |
testcase_21 | AC | 82 ms
6,816 KB |
testcase_22 | AC | 45 ms
6,820 KB |
testcase_23 | AC | 43 ms
6,816 KB |
testcase_24 | AC | 44 ms
6,820 KB |
testcase_25 | AC | 113 ms
6,820 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <algorithm> #include <sstream> #include <cmath> #include <set> #include <iomanip> #include <deque> #include <stdio.h> using namespace std; #define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--) #define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end()) #define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end()) #define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end()) #define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val)) #define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val)) typedef long long ll; /* ll dp[1<<16]; int main(){ int N; cin>>N; dp[(1<<N)-1]=100; for (int i=0; i<(1<<N); i++ ){ } return 0; } */ class Primes { vector<bool> sieve; vector<int> prime; public: Primes(int size){ sieve = *new vector<bool>(size+1,true); sieve[0]=sieve[1]=false; for(long long i=2;i<size+1;i++){ if(sieve[i]){ prime.push_back((int)i); for(long long j=i*i;j<size+1;j+=i)sieve[j]=false; } } } int size(void) { return (int)prime.size(); } int & operator [](int n) { return prime[n]; } bool operator ==(int n) { return sieve[n]; } }; bool judge(set<int> s, int n) { while (n!=0) { if ( s.find(n%10)==s.end() ) { return false; } n /= 10; } return true; } bool same(set<int> a, set<int> b){ if(a.size()!=b.size())return false; for (auto itr1=a.begin(),itr2=b.begin(); itr1!=a.end(); itr1++,itr2++ ){ if( *itr1 != *itr2 ) return false; } return true; } void marge(set<int> &a, int n){ while ( n!=0 ) { a.insert(n%10); n/=10; } } int main(){ Primes p(5000000); int N; cin>>N; set<int> unuse; REP(i,N){ int t; cin>>t; unuse.insert(t); } int ans=-1; int K=1, L=1; set<int> used; for (int i=0; i<p.size(); i++ ) { if( i!=p.size()-1 ) { if ( judge(unuse,p[i]) ){ L = p[i+1]-1; marge(used,p[i]); if ( same(unuse,used) ) { ans = max(ans,abs(K-L)); } }else{ K = p[i]+1; used.clear(); } }else { if ( judge(unuse,p[i]) ){ L = 5000000; marge(used,p[i]); if ( same(used,unuse) ) { ans = max(ans,abs(K-L)); } } } } if ( ans<=0 ) { cout<<-1<<endl; }else{ cout<<ans<<endl; } return 0; }