結果

問題 No.12 限定された素数
ユーザー ktgktg
提出日時 2016-04-25 22:35:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 320 ms / 5,000 ms
コード長 2,641 bytes
コンパイル時間 973 ms
コンパイル使用メモリ 95,784 KB
実行使用メモリ 22,968 KB
最終ジャッジ日時 2024-11-24 08:52:12
合計ジャッジ時間 10,293 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 315 ms
22,708 KB
testcase_01 AC 316 ms
22,712 KB
testcase_02 AC 317 ms
22,828 KB
testcase_03 AC 316 ms
22,804 KB
testcase_04 AC 317 ms
22,836 KB
testcase_05 AC 318 ms
22,840 KB
testcase_06 AC 317 ms
22,840 KB
testcase_07 AC 319 ms
22,832 KB
testcase_08 AC 317 ms
22,708 KB
testcase_09 AC 315 ms
22,836 KB
testcase_10 AC 316 ms
22,836 KB
testcase_11 AC 320 ms
22,836 KB
testcase_12 AC 317 ms
22,964 KB
testcase_13 AC 317 ms
22,708 KB
testcase_14 AC 319 ms
22,704 KB
testcase_15 AC 316 ms
22,836 KB
testcase_16 AC 318 ms
22,964 KB
testcase_17 AC 315 ms
22,836 KB
testcase_18 AC 315 ms
22,968 KB
testcase_19 AC 315 ms
22,960 KB
testcase_20 AC 316 ms
22,708 KB
testcase_21 AC 315 ms
22,708 KB
testcase_22 AC 316 ms
22,836 KB
testcase_23 AC 317 ms
22,704 KB
testcase_24 AC 315 ms
22,836 KB
testcase_25 AC 317 ms
22,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <iterator>

//#define pb push_back
//#define puts(x) cout << #x << " : " << x << endl;
//#pragma GCC diagnostic ignored "-Wconversion"
//#define REP(i,n) for (int i=0;i<(n);i++)
//#define REPE(i,n) for (int i=0;i<=(n);i++)
//#define init(a,b) memset((a), (b), (sizeof(a)));
//#define PI 3.14159265
//#define EPS (1e-10)
//#define EQ(a,b) (abs((a)-(b)) < EPS)

using namespace std;

typedef long long ll;
//#define int long long

typedef pair<int, int> P;

const int PRIME_MAX = 5*1000*1000;
vector<bool> prime_table(PRIME_MAX);
set<int> prime_set;
vector<int> primes;
void make_primes() {
    fill(prime_table.begin(), prime_table.end(), 1);
    prime_table[0] = prime_table[1] = 0;
    for (int i = 2; i <= PRIME_MAX; i++) {
        if (prime_table[i]) {
            prime_set.insert(i);
            primes.push_back(i);
            for (int j = i * 2; j <= PRIME_MAX; j += i) {
                prime_table[j] = 0;
            }
        }
    }
}
string format(int t){
    stringstream ss;
    ss<<t;
    string s;
    ss>>s;
    string ns="";
    for(int i=0;i<s.size();i++)
        if(count(ns.begin(), ns.end(), s[i])==0)
            ns += s[i];
    sort(ns.begin(), ns.end());
    return ns;
}
int tobit_s(string s){
    int k = 0;
    for(int i=0;i<10;i++){
        char c = '0' + i;
        if(count(s.begin(), s.end(), c)>0){
            k |= (1<<i);
        }
    }
    return k;
}
int tobit(int t){
    string s = format(t);
    return tobit_s(s);
}
int bit_tables[400000];
signed main() {
    make_primes();
    for(int i=0;i<primes.size();i++){
        bit_tables[i] = tobit(primes[i]);
    }
//    cout<<primes.size()<<endl;
    int n;cin>>n;
    vector<int> a(n);
    string s="";
    for(int i=0;i<n;i++){
        char c;
        cin>>c;
        s+=c;
    }
    if(n==10){
        cout<<4999999<<endl;
        return 0;
    }
    int want = tobit_s(s);
    ll pn = primes.size();

    int res = -1;
    for(ll i=0;i<pn;i++){
        int k = 0;
        for(ll j = i;j<pn;j++){
            k |= bit_tables[j];
            if((want | k) != want)break;
            if(k == want){
                int lower, upper;
                if(i == 0)lower = 1;
                else lower = primes[i-1]+1;
                if(j == primes.size())upper=5000000;
                else upper = primes[j+1]-1;
                res = max(res, upper-lower);
            }
        }
    }

    cout<<res<<endl;

    return 0;
}
0