結果
問題 | No.6 使いものにならないハッシュ |
ユーザー |
![]() |
提出日時 | 2019-09-08 18:08:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,611 bytes |
コンパイル時間 | 954 ms |
コンパイル使用メモリ | 105,672 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-16 16:50:20 |
合計ジャッジ時間 | 1,949 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <string> #include <iomanip> #include <map> #include <set> #include <cmath> #include <cstdio> using namespace std; #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++) #define All(v) (v).begin(),(v).end() typedef long long ll; vector<bool> sieve(int x){//range...[0,x] vector<bool> flags(x+1,true); flags[0]=false,flags[1]=false; for(int i=2;i*i<=x;i++){ if(!flags[i])continue; for(int mult = i*i;mult<x;mult+=i) flags[mult]=false; } return flags; } int frank_hash(int num){ if(num/10==0)return num; else{ int ret = 0; while(num>0){ ret+=num%10; num/=10; } return frank_hash(ret); } } int main(){ int K,N; cin >> K >> N; auto s = sieve(200000); vector<int> primes; for(int i=K;i<=N;i++){ if(s[i])primes.push_back(i); } int m = primes.size(); vector<int> hashed(m); rep(i,m){ hashed[i]=frank_hash(primes[i]); } int left = 0,right=0; map<int,int> nums; int len = 0,res = 0; for(;right<m;){ if(nums[hashed[right]]==0){ nums[hashed[right]]++; right++; }else if(nums[hashed[left]]!=0){ nums[hashed[left]]--; left++; } if(right-left>=len){ len = right-left; res = primes[left]; } } //rep(i,m)cout << hashed[i] << endl; cout << res << endl; return 0; }