結果

問題 No.12 限定された素数
コンテスト
ユーザー shisyamokongari
提出日時 2016-09-22 18:14:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,515 bytes
コンパイル時間 553 ms
コンパイル使用メモリ 66,860 KB
実行使用メモリ 24,848 KB
最終ジャッジ日時 2024-11-17 13:10:44
合計ジャッジ時間 4,216 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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(cnt==N){
			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&&l!=1){
					ans=2;
				}
				else ans=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]==0) cnt++;
				f[tmp%10]++;
				tmp/=10;
			}
		}
		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