#838873 (Rust) No.2209 Flip and Reverse

• 問題: No.2209 Flip and Reverse
• ユーザー: tomarint
• 提出日時: 2023-02-10 22:04:43
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 13 ms / 2,000 ms
• コード長: 16,523 bytes
• コンパイル時間: 1,875 ms
• コンパイル使用メモリ: 154,620 KB
• 実行使用メモリ: 7,080 KB
• 最終ジャッジ日時: 2023-09-21 23:21:10
• 合計ジャッジ時間: 3,802 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	1 ms; 4,380 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	13 ms; 7,064 KB
testcase_09	AC	1 ms; 4,376 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	1 ms; 4,380 KB
testcase_12	AC	1 ms; 4,376 KB
testcase_13	AC	1 ms; 4,380 KB
testcase_14	AC	13 ms; 7,060 KB
testcase_15	AC	13 ms; 7,072 KB
testcase_16	AC	13 ms; 7,008 KB
testcase_17	AC	13 ms; 7,056 KB
testcase_18	AC	13 ms; 7,056 KB
testcase_19	AC	12 ms; 7,060 KB
testcase_20	AC	13 ms; 7,080 KB
testcase_21	AC	13 ms; 7,080 KB
testcase_22	AC	12 ms; 7,060 KB
testcase_23	AC	12 ms; 7,052 KB
testcase_24	AC	13 ms; 7,056 KB
testcase_25	AC	13 ms; 7,020 KB
testcase_26	AC	12 ms; 7,056 KB
testcase_27	AC	13 ms; 7,060 KB
testcase_28	AC	13 ms; 7,008 KB
testcase_29	AC	13 ms; 7,072 KB
testcase_30	AC	13 ms; 7,056 KB
testcase_31	AC	12 ms; 6,976 KB
testcase_32	AC	13 ms; 7,012 KB
testcase_33	AC	13 ms; 7,064 KB

ソースコード

#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(non_snake_case)]
// use proconio::input;
use std::io::{Read, Write};
use std::mem::swap;
use std::f64::consts::PI;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
//----------------------------------------------------------------------------
fn read<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
//----------------------------------------------------------------------------
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
//----------------------------------------------------------------------------
macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}
//----------------------------------------------------------------------------
const MOD: i64 = 998_244_353;
// const MOD: i64 = 1_000_000_007;

#[derive(Copy, Clone, PartialEq, Eq)]
pub struct Mint {
    val: i64,
}

impl Mint {
    pub fn new(n: i64) -> Self {
        let mut new_val = n % MOD + MOD;
        if new_val >= MOD {
            new_val -= MOD;
        }
        Self { val: new_val }
    }

    pub fn pow(&self, n: i64) -> Self {
        if n == 0 {
            Self { val: 1 }
        } else {
            let mut ret = self.pow(n >> 1);
            ret *= ret;
            if (n & 1) != 0 {
                ret *= *self;
            }
            ret
        }
    }

    pub fn inv(&self) -> Self {
        self.pow(MOD - 2)
    }
}

impl std::fmt::Display for Mint {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}

impl std::fmt::Debug for Mint {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}

impl std::ops::Add for Mint {
    type Output = Self;
    fn add(self, other: Self) -> Self::Output {
        let mut new_val = self.val + other.val;
        if new_val >= MOD {
            new_val -= MOD;
        }
        Self { val: new_val }
    }
}

impl std::ops::Sub for Mint {
    type Output = Self;
    fn sub(self, other: Self) -> Self::Output {
        let mut new_val = self.val + MOD - other.val;
        if new_val >= MOD {
            new_val -= MOD;
        }
        Self { val: new_val }
    }
}

impl std::ops::Mul for Mint {
    type Output = Self;
    fn mul(self, other: Self) -> Self::Output {
        Self {
            val: (self.val * other.val) % MOD,
        }
    }
}

impl std::ops::Div for Mint {
    type Output = Self;
    fn div(self, other: Self) -> Self::Output {
        if other.val == 0 {
            panic!("0 division occured.");
        }
        self * other.inv()
    }
}

impl std::ops::AddAssign for Mint {
    fn add_assign(&mut self, other: Self) {
        *self = *self + other;
    }
}

impl std::ops::SubAssign for Mint {
    fn sub_assign(&mut self, other: Self) {
        *self = *self - other;
    }
}

impl std::ops::MulAssign for Mint {
    fn mul_assign(&mut self, other: Self) {
        *self = *self * other;
    }
}

impl std::ops::DivAssign for Mint {
    fn div_assign(&mut self, other: Self) {
        *self = *self / other;
    }
}
//----------------------------------------------------------------------------
pub struct MintComb {
    fact: Vec<Mint>,
    ifact: Vec<Mint>,
}

impl MintComb {
    pub fn new(n: i64) -> Self {
        let mut obj = Self {
            fact: vec![Mint::new(1); n as usize + 1],
            ifact: vec![Mint::new(1); n as usize + 1],
        };
        assert!(n < MOD);
        obj.fact[0] = Mint::new(1);
        for i in 1..=n as usize {
            obj.fact[i] = obj.fact[i - 1] * Mint::new(i as i64);
        }
        obj.ifact[n as usize] = obj.fact[n as usize].inv();
        for i in (1..=n as usize).rev() {
            obj.ifact[i - 1] = obj.ifact[i] * Mint::new(i as i64);
        }
        obj
    }
    pub fn permutation(&self, n: i64, k: i64) -> Mint {
        assert!(n >= 0);
        if k < 0 || n < k {
            Mint::new(0)
        } else {
            self.fact[n as usize] * self.ifact[k as usize]
        }
    }
    pub fn combination(&self, n: i64, k: i64) -> Mint {
        assert!(n >= 0);
        if k < 0 || n < k {
            Mint::new(0)
        } else {
            self.fact[n as usize] * self.ifact[k as usize] * self.ifact[(n - k) as usize]
        }
    }
}
//----------------------------------------------------------------------------
// 有理数（分数）
#[derive(PartialEq, Debug, Copy, Clone, Eq, PartialOrd, Ord)]
struct Ratio {
    numerator: i64,   // 分子
    denominator: i64, // 分母
}

// ユークリッドの互除法
fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

impl std::fmt::Display for Ratio {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        if self.denominator == 1 {
            write!(f, "{}", self.numerator)
        } else {
            write!(f, "{}/{}", self.numerator, self.denominator)
        }
    }
}

impl Ratio {
    fn new(p: i64, q: i64) -> Ratio {
        if q == 0 {
            panic!("Ratio: divide by zero");
        }
        let g = gcd(p.abs(), q.abs());
        let s = if q < 0 { -1 } else { 1 };
        Ratio {
            numerator: s * p / g,
            denominator: s * q / g,
        }
    }

    fn from_integer(n: i64) -> Ratio {
        Ratio {
            numerator: n,
            denominator: 1,
        }
    }

    fn as_int(&self) -> i64 {
        self.numerator / self.denominator
    }
    fn as_float(&self) -> f64 {
        self.numerator as f64 / self.denominator as f64
    }

    fn numer(&self) -> i64 {
        self.numerator
    }
    fn denom(&self) -> i64 {
        self.denominator
    }

    fn is_integer(&self) -> bool {
        self.denominator == 1
    }
}

impl std::ops::Add for Ratio {
    type Output = Ratio;
    fn add(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.denominator + other.numerator * self.denominator;
        let q = self.denominator * other.denominator;
        Ratio::new(p, q)
    }
}

impl std::ops::Sub for Ratio {
    type Output = Ratio;
    fn sub(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.denominator - other.numerator * self.denominator;
        let q = self.denominator * other.denominator;
        Ratio::new(p, q)
    }
}

impl std::ops::Mul for Ratio {
    type Output = Ratio;
    fn mul(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.numerator;
        let q = self.denominator * other.denominator;
        Ratio::new(p, q)
    }
}

impl std::ops::Div for Ratio {
    type Output = Ratio;
    fn div(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.denominator;
        let q = self.denominator * other.numerator;
        Ratio::new(p, q)
    }
}
//----------------------------------------------------------------------------
pub trait BinarySearch<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                std::cmp::Ordering::Less => {
                    low = mid + 1;
                }
                std::cmp::Ordering::Equal | std::cmp::Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                std::cmp::Ordering::Less | std::cmp::Ordering::Equal => {
                    low = mid + 1;
                }
                std::cmp::Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
//----------------------------------------------------------------------------
pub trait LexicalPermutation {
    /// Return `true` if the slice was permuted, `false` if it is already
    /// at the last ordered permutation.
    fn next_permutation(&mut self) -> bool;
    /// Return `true` if the slice was permuted, `false` if it is already
    /// at the first ordered permutation.
    fn prev_permutation(&mut self) -> bool;
}

impl<T> LexicalPermutation for [T]
where
    T: Ord,
{
    /// Original author in Rust: Thomas Backman <[e-mail]>
    fn next_permutation(&mut self) -> bool {
        // These cases only have 1 permutation each, so we can't do anything.
        if self.len() < 2 {
            return false;
        }

        // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
        let mut i = self.len() - 1;
        while i > 0 && self[i - 1] >= self[i] {
            i -= 1;
        }

        // If that is the entire vector, this is the last-ordered permutation.
        if i == 0 {
            return false;
        }

        // Step 2: Find the rightmost element larger than the pivot (i-1)
        let mut j = self.len() - 1;
        while j >= i && self[j] <= self[i - 1] {
            j -= 1;
        }

        // Step 3: Swap that element with the pivot
        self.swap(j, i - 1);

        // Step 4: Reverse the (previously) weakly decreasing part
        self[i..].reverse();

        true
    }

    fn prev_permutation(&mut self) -> bool {
        // These cases only have 1 permutation each, so we can't do anything.
        if self.len() < 2 {
            return false;
        }

        // Step 1: Identify the longest, rightmost weakly increasing part of the vector
        let mut i = self.len() - 1;
        while i > 0 && self[i - 1] <= self[i] {
            i -= 1;
        }

        // If that is the entire vector, this is the first-ordered permutation.
        if i == 0 {
            return false;
        }

        // Step 2: Reverse the weakly increasing part
        self[i..].reverse();

        // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
        let mut j = self.len() - 1;
        while j >= i && self[j - 1] < self[i - 1] {
            j -= 1;
        }

        // Step 4: Swap that element with the pivot
        self.swap(i - 1, j);

        true
    }
}
//----------------------------------------------------------------------------
// Binary Indexed Tree（BIT, Fenwick Tree）
#[derive(Clone)]
struct FenwickTree {
    n: usize,
    data: Vec<i64>,
}
impl FenwickTree {
    fn new(n: usize) -> FenwickTree {
        FenwickTree {
            n: n,
            data: vec![0; n + 1],
        }
    }
    // --- sum ---
    fn add(&mut self, i: usize, x: i64) {
        let mut i = i + 1;
        while i <= self.n {
            self.data[i] += x;
            i += i & i.wrapping_neg();
        }

    }
    fn sum(&self, i: usize) -> i64 {
        let mut i = i + 1;
        let mut s = 0;
        while i > 0 {
            s += self.data[i];
            i -= i & i.wrapping_neg();
        }
        s
    }
    // --- max ---
    fn update(&mut self, i: usize, x: i64) {
        let mut i = i + 1;
        while i <= self.n {
            self.data[i] = self.data[i].max(x);
            i += i & i.wrapping_neg();
        }
    }
    fn max(&self, i: usize) -> i64 {
        let mut i = i + 1;
        let mut s = 0;
        while i > 0 {
            s = s.max(self.data[i]);
            i -= i & i.wrapping_neg();
        }
        s
    }
}
//----------------------------------------------------------------------------
struct UnionFind {
    n: usize,
    parent: Vec<i64>,
}
impl UnionFind {
    fn new(n: usize) -> Self {
        Self {
            n,
            parent: vec![-1; n + 1],
        }
    }
    fn root(&mut self, a: usize) -> usize {
        if self.parent[a] < 0 {
            return a;
        }
        self.parent[a] = self.root(self.parent[a] as usize) as i64;
        return self.parent[a] as usize;
    }
    fn size(&mut self, a: usize) -> usize {
        let r = self.root(a);
        return -self.parent[r] as usize;
    }
    fn connect(&mut self, a: usize, b: usize) -> bool {
        let a = self.root(a);
        let b = self.root(b);
        if a == b {
            return false;
        }
        if self.size(a) > self.size(b) {
            self.parent[a] += self.parent[b];
            self.parent[b] = a as i64;
        } else {
            self.parent[b] += self.parent[a];
            self.parent[a] = b as i64;
        }
        return true;
    }
}
//----------------------------------------------------------------------------
macro_rules! printvec {
    ($vec:expr) => {{
        print!(
            "{}",
            $vec.iter()
                .map(|&x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    }};
}
macro_rules! printvecln {
    ($vec:expr) => {{
        printvec!($vec);
        println!();
    }};
}
//----------------------------------------------------------------------------
fn main() {
    let mut solver = Solver::new();
    solver.run();
}
//----------------------------------------------------------------------------
const INF: i64 = 2222222222222222222;
//----------------------------------------------------------------------------
#[derive(Default)]
struct Solver {
}
impl Solver {
    pub fn new() -> Self {
        Self {  }
    }

    pub fn run(&mut self) {
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        let mut sc = scanner::Scanner::new(&s);
        let out = std::io::stdout();
        let mut out = std::io::BufWriter::new(out.lock());
        self.solve(&mut sc, &mut out);
    }

    fn solve<W: std::io::Write>(&mut self, sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
        let N: usize = sc.next();
        let S: String = sc.next();
        let T: String = sc.next();
        let S = S.as_bytes();
        let T = T.as_bytes();
        let mut cnt = 0;
        for i in 0..N {
            if S[i] != T[i] {
                cnt += 1;
            }
        }
        let S: Vec<u8> = if cnt % 2 != 0 {
            S.iter().rev().map(|x| *x).collect()
        } else {
            S.iter().map(|x| *x).collect()
        };
        let mut ans = 0;
        for i in 0..N {
            if S[i] != T[i] {
                ans += 1;
            }
        }
        writeln!(out, "{}", ans).ok();
    }
}