Submission #5626360


Source Code Expand

Copy
use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let s: Vec<usize> = sc
        .chars()
        .into_iter()
        .map(|c| c as usize - 'a' as usize)
        .collect();
    let n = s.len();
    let mut prefix_dp = vec![n as u32; 1 << 26];
    for i in 0..26 {
        prefix_dp[1 << i] = 1;
    }
    prefix_dp[0] = 1;

    let mut cur = 0;
    for c in s.into_iter() {
        cur ^= 1 << c;
        let mut min = prefix_dp[cur];
        for i in 0..26 {
            let suffix = 1 << i;
            let prefix = cur ^ suffix;
            min = cmp::min(min, prefix_dp[prefix] + 1);
        }
        prefix_dp[cur] = min;
    }

    println!("{}", prefix_dp[cur]);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Submission Info

Submission Time
Task D - Yet Another Palindrome Partitioning
User kenkoooo
Language Rust (1.15.1)
Score 0
Code Size 1597 Byte
Status
Exec Time 183 ms
Memory 268540 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0 / 700 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt, 1_72.txt, 1_73.txt, 1_74.txt, 1_75.txt, 1_76.txt, 1_77.txt
Case Name Status Exec Time Memory
0_00.txt 65 ms 266492 KB
0_01.txt 65 ms 266492 KB
0_02.txt 65 ms 266492 KB
0_03.txt 65 ms 266492 KB
1_00.txt 65 ms 266492 KB
1_01.txt 65 ms 266492 KB
1_02.txt 65 ms 266492 KB
1_03.txt 65 ms 266492 KB
1_04.txt 65 ms 266492 KB
1_05.txt 65 ms 266492 KB
1_06.txt 65 ms 266492 KB
1_07.txt 65 ms 266492 KB
1_08.txt 125 ms 268540 KB
1_09.txt 95 ms 268540 KB
1_10.txt 95 ms 268540 KB
1_11.txt 93 ms 268540 KB
1_12.txt 90 ms 268540 KB
1_13.txt 91 ms 268540 KB
1_14.txt 91 ms 268540 KB
1_15.txt 96 ms 268540 KB
1_16.txt 93 ms 268540 KB
1_17.txt 95 ms 268540 KB
1_18.txt 97 ms 268540 KB
1_19.txt 97 ms 268540 KB
1_20.txt 95 ms 268540 KB
1_21.txt 96 ms 268540 KB
1_22.txt 123 ms 268540 KB
1_23.txt 111 ms 268540 KB
1_24.txt 120 ms 268540 KB
1_25.txt 148 ms 268540 KB
1_26.txt 120 ms 268540 KB
1_27.txt 155 ms 268540 KB
1_28.txt 131 ms 268540 KB
1_29.txt 121 ms 268540 KB
1_30.txt 158 ms 268540 KB
1_31.txt 147 ms 268540 KB
1_32.txt 164 ms 268540 KB
1_33.txt 154 ms 268540 KB
1_34.txt 171 ms 268540 KB
1_35.txt 183 ms 268540 KB
1_36.txt 180 ms 268540 KB
1_37.txt 181 ms 268540 KB
1_38.txt 113 ms 268540 KB
1_39.txt 111 ms 268540 KB
1_40.txt 112 ms 268540 KB
1_41.txt 112 ms 268540 KB
1_42.txt 107 ms 268540 KB
1_43.txt 106 ms 268540 KB
1_44.txt 107 ms 268540 KB
1_45.txt 107 ms 268540 KB
1_46.txt 102 ms 268540 KB
1_47.txt 103 ms 268540 KB
1_48.txt 103 ms 268540 KB
1_49.txt 102 ms 268540 KB
1_50.txt 101 ms 268540 KB
1_51.txt 100 ms 268540 KB
1_52.txt 100 ms 268540 KB
1_53.txt 99 ms 268540 KB
1_54.txt 100 ms 268540 KB
1_55.txt 98 ms 268540 KB
1_56.txt 100 ms 268540 KB
1_57.txt 98 ms 268540 KB
1_58.txt 99 ms 268540 KB
1_59.txt 98 ms 268540 KB
1_60.txt 99 ms 268540 KB
1_61.txt 99 ms 268540 KB
1_62.txt 98 ms 268540 KB
1_63.txt 96 ms 268540 KB
1_64.txt 97 ms 268540 KB
1_65.txt 98 ms 268540 KB
1_66.txt 97 ms 268540 KB
1_67.txt 95 ms 268540 KB
1_68.txt 95 ms 268540 KB
1_69.txt 96 ms 268540 KB
1_70.txt 97 ms 268540 KB
1_71.txt 97 ms 268540 KB
1_72.txt 95 ms 268540 KB
1_73.txt 95 ms 268540 KB
1_74.txt 95 ms 268540 KB
1_75.txt 95 ms 268540 KB
1_76.txt 95 ms 268540 KB
1_77.txt 97 ms 268540 KB