結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー srtry
提出日時 2025-12-05 20:50:08
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,944 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,760 ms
コンパイル使用メモリ 398,232 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-05 20:50:23
合計ジャッジ時間 13,437 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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: 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 mem:usize = 1<<(primes[0].1);
    loop {
        if r-l+1 >= max_len {
            max_len = r-l+1;
            ans = primes[l].0;
        }
        if r==primes.len()-1 {
            break;
        }
        match (mem&(1<<primes[r+1].1)==0, l==r, primes[r].1==primes[r+1].1) {
            (false,false,_) => {
                mem ^= 1<<primes[l].1;
                l += 1;
            }
            (_,true,true) => {
                r += 1;
                l += 1;
            }
            _ => {
                r += 1;
                mem |= 1<<primes[r].1;
            }
        }
    }

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