結果

問題 No.2890 Chiffon
ユーザー naut3
提出日時 2024-09-13 22:47:18
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 2,579 bytes
コンパイル時間 15,396 ms
コンパイル使用メモリ 379,432 KB
実行使用メモリ 545,712 KB
最終ジャッジ日時 2024-09-13 22:47:39
合計ジャッジ時間 20,367 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 MLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case)]
#[allow(unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
    input! {
        N: usize, K: usize,
        A: [usize; K],
    }

    let mut B = A
        .iter()
        .cloned()
        .collect::<std::collections::BTreeSet<usize>>();

    for a in A.iter() {
        B.insert(a + 2 * N);
    }

    let mut ok = 1;
    let mut ng = N + 1;

    while ng - ok > 1 {
        let m = (ok + ng) / 2;

        let mut nxt = vec![0; 4 * N + 1];
        nxt[4 * N] = 4 * N;

        for i in (0..4 * N).step_by(2) {
            // i + m がok か
            if i + m < 4 * N && B.range(i + 1..i + m).next().is_some() {
                nxt[i] = if m % 2 == 0 { i + m } else { i + m + 1 };
            } else {
                let n = B.range(i + m..).next();

                if let Some(&n) = n {
                    nxt[i] = n + 1;
                } else {
                    nxt[i] = 4 * N;
                }
            }
        }

        // eprintln!(
        //     "{} | {}",
        //     m,
        //     nxt.iter()
        //         .map(|x| x.to_string())
        //         .collect::<Vec<_>>()
        //         .join(" ")
        // );

        let dbl = Doubling::build(&nxt, 30);

        let mut isok = false;

        for i in (0..2 * N).step_by(2) {
            let n = dbl.next(i, K as u64);

            if n <= i + 2 * N {
                isok = true;
                break;
            }
        }

        if isok {
            ok = m;
        } else {
            ng = m;
        }
    }

    println!("{}", ok);
}

pub type Index = usize;

pub struct Doubling {
    dp: Vec<Index>,
    pub size: usize,
    pub depth: Index,
}

impl Doubling {
    pub fn build(nxt: &[Index], depth: Index) -> Self {
        let size = nxt.len();

        let mut dp = nxt.to_vec();
        dp.append(&mut vec![0; size * depth as usize]);

        for d in 0..depth as usize {
            for i in 0..size {
                dp[(d + 1) * size + i] = dp[d * size + dp[d * size + i] as usize];
            }
        }

        Self { dp, size, depth }
    }

    pub fn next(&self, mut src: Index, k: u64) -> Index {
        assert!(k < 1 << (self.depth + 1));

        for i in 0..self.depth {
            if (k >> i) & 1 == 1 {
                src = self.dp[i as usize * self.size + src as usize];
            }
        }

        src
    }

    pub fn jump_power_of_two(&self, src: Index, k: Index) -> Index {
        assert!(k <= self.depth);
        self.dp[k as usize * self.size + src as usize]
    }
}
0