結果

問題 No.12 限定された素数
ユーザー shisyamokongarishisyamokongari
提出日時 2016-09-22 18:19:06
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,513 bytes
コンパイル時間 651 ms
コンパイル使用メモリ 66,988 KB
実行使用メモリ 24,848 KB
最終ジャッジ日時 2024-05-01 15:26:06
合計ジャッジ時間 5,210 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 111 ms
24,724 KB
testcase_01 AC 122 ms
24,720 KB
testcase_02 AC 136 ms
24,720 KB
testcase_03 AC 120 ms
24,592 KB
testcase_04 AC 121 ms
24,720 KB
testcase_05 AC 154 ms
24,720 KB
testcase_06 AC 138 ms
24,592 KB
testcase_07 AC 118 ms
24,720 KB
testcase_08 AC 115 ms
24,596 KB
testcase_09 AC 117 ms
24,588 KB
testcase_10 AC 125 ms
24,720 KB
testcase_11 AC 119 ms
24,720 KB
testcase_12 AC 144 ms
24,720 KB
testcase_13 AC 143 ms
24,848 KB
testcase_14 AC 141 ms
24,596 KB
testcase_15 AC 116 ms
24,720 KB
testcase_16 AC 136 ms
24,588 KB
testcase_17 AC 124 ms
24,596 KB
testcase_18 AC 128 ms
24,720 KB
testcase_19 AC 112 ms
24,720 KB
testcase_20 AC 126 ms
24,716 KB
testcase_21 AC 140 ms
24,716 KB
testcase_22 AC 127 ms
24,720 KB
testcase_23 AC 113 ms
24,720 KB
testcase_24 WA -
testcase_25 AC 120 ms
24,604 KB
権限があれば一括ダウンロードができます

ソースコード

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;
			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