結果

問題 No.12 限定された素数
ユーザー shisyamokongarishisyamokongari
提出日時 2016-09-22 17:41:51
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,229 bytes
コンパイル時間 587 ms
コンパイル使用メモリ 68,984 KB
実行使用メモリ 24,688 KB
最終ジャッジ日時 2023-08-11 01:17:34
合計ジャッジ時間 4,229 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
24,668 KB
testcase_01 WA -
testcase_02 AC 71 ms
24,464 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 75 ms
24,628 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){
		//cout<<l<<","<<r<<"|"<<sosuu[l]<<","<<sosuu[r]<<"||"<<cnt<<"<"<<ans<<endl;
		if(l>=sosuu.size()||r>=sosuu.size()) break;
		if(cnt<N){
			r++;
			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;
				}
			}
			else{
				l=r+1,r=l+1;
				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;
				}
			}
		}
		else{
			if(N!=1&&(sosuu[r]-sosuu[l]>ans||ans==-1)) ans=sosuu[r]-sosuu[l];
			if(N==1){
				if(l!=0){
					ans=2;
				}
			}
			int tmp=sosuu[l];
			if(r!=l){
				while(tmp!=0){
					f[tmp%10]--;
					if(f[tmp%10]==0) cnt--;
					tmp/=10;
				}	
				l++;
			}
			else{
				l++,r++;
				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