結果

問題 No.3290 Encrypt Failed, but Decrypt Succeeded
ユーザー Plan8
提出日時 2025-10-18 13:30:57
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,465 bytes
コンパイル時間 12,280 ms
コンパイル使用メモリ 400,948 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-18 13:31:12
合計ジャッジ時間 14,526 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 6 WA * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: field `all` is never read
  --> src/main.rs:12:5
   |
8  | struct Solver {
   |        ------ field in this struct
...
12 |     all: Vec<String>,
   |     ^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: method `dfs` is never used
  --> src/main.rs:85:8
   |
15 | impl Solver {
   | ----------- method in this implementation
...
85 |     fn dfs(&mut self, pos: usize, cur: &mut String) {
   |        ^^^

ソースコード

diff # 

use proconio::input;

fn main() {
    let ans = Solver::new().solve();
    println!("{}", ans);
}

struct Solver {
    n: usize,
    s: String,
    k: u64,
    all: Vec<String>,
}

impl Solver {
    fn new() -> Self {
        input! {
            n: usize,
            k: u64,
            s: String,
        }
        Self {
            n,
            s,
            k,
            all: vec![],
        }
    }

    fn solve(&mut self) -> String {
        // let mut cur = "".to_string();
        // self.dfs(0, &mut cur);
        // self.all.sort();
        // return self.all[(self.k - 1) as usize].clone();
        let mut ans = "".to_string();
        let dp = self.count();
        let mut pos = 0;
        let mut res = self.k;

        while pos < self.n {
            for len in 1..=2 {
                if !self.to_num_ok(pos, len) {
                    continue;
                }
                let cnt = dp[pos + len];
                if cnt < res {
                    res -= cnt;
                    continue;
                }
                ans.push(
                    self.s[pos..pos + len]
                        .parse::<u8>()
                        .map(|x| (b'a' + x - 1) as char)
                        .unwrap(),
                );
                pos += len;
                break;
            }
        }

        ans
    }

    fn count(&self) -> Vec<u64> {
        let mut dp = vec![0u64; self.n + 1];
        dp[self.n] = 1;
        for i in (0..self.n).rev() {
            for len in 1..=2 {
                if self.to_num_ok(i, len) {
                    dp[i] = dp[i].saturating_add(dp[i + len]);
                }
            }
        }
        dp
    }

    fn to_num_ok(&self, i: usize, len: usize) -> bool {
        if i + len > self.n {
            return false;
        }
        let sub = &self.s[i..i + len];
        sub.parse::<u8>().is_ok_and(|x| (1..=26).contains(&x))
    }

    fn dfs(&mut self, pos: usize, cur: &mut String) {
        if pos == self.n {
            self.all.push(cur.clone());
            return;
        }
        for len in 1..=2 {
            if self.to_num_ok(pos, len) {
                cur.push(
                    self.s[pos..pos + len]
                        .parse::<u8>()
                        .map(|x| (b'a' + x - 1) as char)
                        .unwrap(),
                );
                self.dfs(pos + len, cur);
                cur.pop();
            }
        }
    }
}
0