結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー srtry
提出日時 2025-12-05 20:22:29
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,092 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 24,402 ms
コンパイル使用メモリ 397,700 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-05 20:22:55
合計ジャッジ時間 14,780 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused imports: `HashMap` and `HashSet`
 --> src/main.rs:8:24
  |
8 | use std::collections::{HashSet, HashMap};
  |                        ^^^^^^^  ^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::iter`
 --> src/main.rs:9:5
  |
9 | use std::iter;
  |     ^^^^^^^^^

warning: value assigned to `primes` is never read
  --> src/main.rs:15:13
   |
15 |     let mut primes:Vec<usize> = Vec::new();
   |             ^^^^^^
   |
   = help: maybe it is overwritten before being read?
   = note: `#[warn(unused_assignments)]` on by default

warning: unused variable: `e_k`
  --> src/main.rs:30:19
   |
30 |         .filter(|(e_k,&e_v)| e_v)
   |                   ^^^ help: if this is intentional, prefix it with an underscore: `_e_k`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `e_v`
  --> src/main.rs:31:20
   |
31 |         .map(|(e_k,e_v)| e_k)
   |                    ^^^ help: if this is intentional, prefix it with an underscore: `_e_v`

warning: unused variable: `is_end`
  --> src/main.rs:60:13
   |
60 |     let mut is_end = false;
   |             ^^^^^^ help: if this is intentional, prefix it with an underscore: `_is_end`

warning: variable does not need to be mutable
  --> src/main.rs:60:9
   |
60 |     let mut is_end = false;
   |         ----^^^^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: constant `big` is never used
  --> src/main.rs:12:7
   |
12 | const big:usize = 200001;
   |       ^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: constant `big` should have an upper case name
  --> src/main.rs:12:7
   |
12 | const big:usize = 200001;
   |       ^^^ help: convert the identifier to upper case: `BIG`
   |
   = note: `#[warn(non_upper_case_globals)]` on by default

ソースコード

diff #
raw source code 

/* 
 *     Author:  srtry
 *     Created: 2025-10-17T21:49:35+09:00
 *     Coding:  utf-8-unix
 */

use proconio::input;
use std::collections::{HashSet, HashMap};
use std::iter;
use std::io::{stdout,Write,BufWriter};

const big:usize = 200001;

fn primes_leq(&n:&usize) -> Vec<usize> {
    let mut primes:Vec<usize> = Vec::new();
    let mut is_prime:Vec<bool> = vec![true;n+1];
    is_prime[0] = false;
    is_prime[1] = false;
    let limit:usize = (n as f64).sqrt() as usize;
    for i in 2..=limit {
        if is_prime[i] {            
            for j in i..=n/i {
                is_prime[i*j] = false;
            }
        }
    }
    primes = is_prime
        .iter()
        .enumerate()
        .filter(|(e_k,&e_v)| e_v)
        .map(|(e_k,e_v)| e_k)
        .collect();
    return primes;
}

fn main() {
    input!{
        k:usize,
        n:usize
    }

    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    
    let primes:Vec<(usize,usize)> = primes_leq(&n)
        .iter()
        .filter(|&e| e>=&k)
        .map(|&e| (e, {if e==0 {9} else {(e-1)%9+1}}))
        .collect();
    let mut ans = primes[0].0;

    if primes.len()==1 {
        write!(out, "{}", ans).unwrap();
        return;
    }

    let mut max_len = 1;
    let mut r = 0;
    let mut l= 0;
    let mut is_end = false;
    // mem[hash] = primes index
    let mut mem:[isize;10] = [-1;10];
    mem[primes[0].1] = 0;

    loop {            
        // max_len更新
        if r-l+1 >= max_len {
            max_len = r-l+1;
            ans = primes[l].0;
        }
        if r==primes.len()-1 {
            break;
        }
        // // lr更新
        match (mem[primes[r+1].1]==-1, l==r, primes[r].1==primes[r+1].1) {
            (false,false,_) => {
                mem[primes[l].1] = -1;
                l += 1;
            }
            (_,true,true) => {
                r += 1;
                l += 1;
            }
            _ => {
                r += 1;
                mem[primes[r].1] = r as isize;
            }
        }
    }

    write!(out, "{}", ans).unwrap();
}
0