結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー togatoga
提出日時 2015-08-23 15:56:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,432 bytes
コンパイル時間 1,195 ms
コンパイル使用メモリ 165,072 KB
実行使用メモリ 78,856 KB
最終ジャッジ日時 2024-09-16 16:28:53
合計ジャッジ時間 9,448 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 10 TLE * 1 -- * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int sieve(int)’:
main.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
   19 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200010;
int K,N;
vector<int> prime;
bool flag[MAX_N];
int sieve(int N){
  memset(flag, true, sizeof(flag));
  for (int i = 2; i <= N; i++){
    if (flag[i]){
      if (K <= i)prime.push_back(i);
      for (int j = i + i; j <= N; j+= i){
	flag[j] = false;
      }
    }
  }
}

int calc(int num){

  while (true){
    int res = 0;
    while (num){
      res += num % 10;
      num /= 10;
    }
    if (res <= 9)return res;
    num = res;
  }
}

int main(){

  cin >> K >> N;
  sieve(N);
  vector<int> array;
  for (int i = 0; i < prime.size(); i++){
    array.push_back(calc(prime[i]));
  }
  int head = 0;
  int tail = 0;
  set<int> used;
  int ans = 0;
  int ansele = -1;
  // for (const auto &val : prime){
  //   printf("%02d ", val);
  // }
  // cout << endl;
  // for (const auto &val : array){
  //   printf("%02d ", val);

  // }
  // cout << endl;
  while (tail < array.size()){
    if (used.count(array[tail]) == 0){
      used.insert(array[tail++]);
      if (ans < (tail - head)){
	ans = tail - head;
	ansele = prime[head];
      }else if (ans == (tail - head) && ansele < prime[head]){
	ans = tail - head;
	ansele = prime[head];
      }
    }else{
      while (true){
	if (head == tail)break;
	if (array[head] == array[tail]){
	  used.erase(array[head++]);
	  break;
	}else{
	  used.erase(array[head++]);
	}
      }
    }

  }
  cout << ansele << endl;
}
0