結果

問題 No.12 限定された素数
ユーザー shisyamokongarishisyamokongari
提出日時 2016-09-22 17:57:09
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,468 bytes
コンパイル時間 566 ms
コンパイル使用メモリ 65,916 KB
実行使用メモリ 24,852 KB
最終ジャッジ日時 2024-11-17 13:09:50
合計ジャッジ時間 3,776 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 91 ms
24,668 KB
testcase_02 AC 89 ms
24,724 KB
testcase_03 AC 92 ms
24,716 KB
testcase_04 WA -
testcase_05 AC 93 ms
24,720 KB
testcase_06 AC 90 ms
24,716 KB
testcase_07 AC 90 ms
24,708 KB
testcase_08 AC 92 ms
24,592 KB
testcase_09 AC 95 ms
24,720 KB
testcase_10 WA -
testcase_11 AC 88 ms
24,596 KB
testcase_12 AC 93 ms
24,716 KB
testcase_13 AC 93 ms
24,724 KB
testcase_14 AC 95 ms
24,716 KB
testcase_15 AC 96 ms
24,508 KB
testcase_16 AC 91 ms
24,720 KB
testcase_17 AC 85 ms
24,716 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

#define NMAX 5000000

int main(){

	vector<int> sosuu;
	int hurui[NMAX+1];
	int N,A[10];

	for(int i=0;i<=NMAX;i++) hurui[i]=0;
	hurui[0]=1,hurui[1]=1;

	for(int i=0;i<=NMAX;i++){
		if(hurui[i]==0){
			sosuu.push_back(i);
			for(int j=i*2;j<NMAX;j+=i) hurui[j]=1;
		}
	}

	cin>>N;

	for(int i=0;i<N;i++) cin>>A[i];

	int l=0,r=0;
	int f[10];
	bool ok[10];
	for(int i=0;i<10;i++) f[i]=0,ok[i]=false;
	for(int i=0;i<N;i++) ok[A[i]]=true;
	int cnt=0;
	int ans=-1;

	
	while(1){
		if(l>=sosuu.size()||r>=sosuu.size()) break;
		bool ff=true;
		int tmp=sosuu[l];
		while(tmp!=0){
			if(!ok[tmp%10]) ff=false;
			tmp/=10;
		}
		if(ff){
			tmp=sosuu[r];
			while(tmp!=0){
				if(!ok[tmp%10]) ff=false;
				tmp/=10;
			}
			if(ff) break;
			else l=r+1,r=l;
		}
		else l++,r++;
	}

	if(l>=sosuu.size()||r>=sosuu.size()){
		cout<<ans<<endl;
		return 0;
	}

	int tmp=sosuu[r];
	while(tmp!=0){
		if(!f[tmp%10]) cnt++,f[tmp%10]++;
		tmp/=10;
	}
	tmp=sosuu[l];
	while(tmp!=0){
		if(!f[tmp%10]) cnt++,f[tmp%10]++;
		tmp/=10;
	}

	/*ssssssssssssssssssssssss*/
	while(1){
		if(l>=sosuu.size()||r>=sosuu.size()) break;
		//cout<<l<<","<<r<<"|"<<sosuu[l]<<","<<sosuu[r]<<"||"<<cnt<<"<"<<ans<<endl;
		r++;
		if(l>=sosuu.size()||r>=sosuu.size()) break;
		bool ff=true;
		tmp=sosuu[r];
		while(tmp!=0){
			if(!ok[tmp%10]) ff=false;
			tmp/=10;
		}
		if(ff){
			int tmp=sosuu[r];
			while(tmp!=0){
				if(!f[tmp%10]) cnt++,f[tmp%10]++;
				tmp/=10;
			}
			int L,R;
			if(l==0) L=1;
			else L=sosuu[l-1]+1;
			if(r==sosuu.size()-1) R=NMAX;
			else R=sosuu[r+1]-1;

			if(N!=1&&(R-L>ans||ans==-1)) ans=R-L;
			if(N==1){
				if(l!=0){
					ans=2;
				}
			}
		}
		else{
			l=r+1,r=l+1;
			if(l>=sosuu.size()||r>=sosuu.size()) break;
			for(int i=0;i<10;i++) f[i]=0;
			cnt=0;
			while(1){
				if(l>=sosuu.size()||r>=sosuu.size()) break;
				bool ff=true;
				int tmp=sosuu[l];
				while(tmp!=0){
					if(!ok[tmp%10]) ff=false;
					tmp/=10;
				}		
				if(ff){
					tmp=sosuu[r];
					while(tmp!=0){
						if(!ok[tmp%10]) ff=false;
						tmp/=10;
					}
					if(ff) break;
					else l=r+1,r=l;
				}
				else l++,r++;
			}

			if(l>=sosuu.size()||r>=sosuu.size()){
				cout<<ans<<endl;
				return 0;
			}

			int tmp=sosuu[r];
			while(tmp!=0){
				if(!f[tmp%10]) cnt++,f[tmp%10]++;
				tmp/=10;
			}
			tmp=sosuu[l];
			while(tmp!=0){
				if(!f[tmp%10]) cnt++,f[tmp%10]++;
				tmp/=10;
			}
		}
	}

	cout<<ans<<endl;
}
0