結果

問題 No.2890 Chiffon
ユーザー naut3naut3
提出日時 2024-09-13 22:47:18
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,624 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 0 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 1 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 MLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
権限があれば一括ダウンロードができます

ソースコード

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