結果

問題 No.262 面白くないビットすごろく
ユーザー akakimidoriakakimidori
提出日時 2022-06-15 09:33:33
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,158 bytes
コンパイル時間 13,111 ms
コンパイル使用メモリ 379,636 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-03 18:52:08
合計ジャッジ時間 13,231 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin recurse ----------
// reference
// https://twitter.com/noshi91/status/1393952665566994434
// https://twitter.com/shino16_cp/status/1393933468082397190
pub fn recurse<A, R, F>(f: F) -> impl Fn(A) -> R
where
    F: Fn(&dyn Fn(A) -> R, A) -> R,
{
    fn call<A, R, F>(f: &F, a: A) -> R
    where
        F: Fn(&dyn Fn(A) -> R, A) -> R,
    {
        f(&|a| call(f, a), a)
    }
    move |a| call(&f, a)
}
// ---------- end recurse ----------

fn read() -> usize {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().unwrap()
}

use std::cell::*;

type Map<K, V> = std::collections::HashMap<K, V>;

fn main() {
    let n = read();
    // dp[(a, b, c)] = (x, y)
    // 下位a bit の値がb, 上位bitの1の個数がc の時
    // 2^a に寄与が発生するまでに振る回数、足し込まれる値
    let dp = RefCell::new(Map::<(usize, usize, usize), (usize, usize)>::new());
    let up = 7;
    let calc = recurse(|rec, (a, b, c): (usize, usize, usize)| -> (usize, usize) {
        if let Some(&p) = dp.borrow().get(&(a, b, c)) {
            return p;
        }
        assert!(a >= up);
        assert!(b < (1 << up));
        assert!(c > 0 || b > 0);
        let ans = if a == up {
            let mut now = b;
            let mut x = 0;
            while now < 1 << a {
                let v = now.count_ones() as usize + c;
                now += v;
                x += 1;
            }
            (x, now - b)
        } else {
            let p = rec((a - 1, b, c));
            let q = rec((a - 1, (b + p.1) % (1 << (a - 1)), c + 1));
            (p.0 + q.0, p.1 + q.1)
        };
        dp.borrow_mut().insert((a, b, c), ans);
        ans
    });
    let mut now = 1;
    let mut ans = 1;
    for i in (up..40).rev() {
        let (x, y) = calc((i, now % (1 << i), (now >> i).count_ones() as usize));
        if now + y < n {
            now += y;
            ans += x;
        }
    }
    while now < n {
        now += now.count_ones() as usize;
        ans += 1;
    }
    let mut ans = ans as i64;
    if now != n {
        ans = -1;
    }
    println!("{}", ans);
}
0