#861065 (Rust) No.2239 Friday

提出ソース
結果

問題	No.2239 Friday
コンテスト
ユーザー	tipstar0125
提出日時	2023-04-21 15:43:53
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	14,823 bytes
コンパイル時間	21,559 ms
コンパイル使用メモリ	391,300 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-11-06 10:33:41
合計ジャッジ時間	17,887 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 20
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #![allow(non_snake_case)]
// #![allow(unused_imports)]
// #![allow(unused_macros)]
// #![allow(clippy::needless_range_loop)]
// #![allow(clippy::comparison_chain)]
// #![allow(clippy::nonminimal_bool)]
// #![allow(clippy::neg_multiply)]
// #![allow(dead_code)]
// use std::collections::{BTreeMap, VecDeque};

// use std::io;
// use std::str::FromStr;

// fn read_line() -> String {
//     let mut buffer = String::new();
//     io::stdin()
//         .read_line(&mut buffer)
//         .expect("failed to read line");

//     buffer
// }

// fn read<T: FromStr>() -> Result<T, T::Err> {
//     read_line().trim().parse::<T>()
// }

// fn read_vec<T: FromStr>() -> Result<Vec<T>, T::Err> {
//     read_line()
//         .split_whitespace()
//         .map(|x| x.parse::<T>())
//         .collect()
// }

// #[macro_export]
// macro_rules! max {
//     ($x: expr) => ($x);
//     ($x: expr, $( $y: expr ),+) => {
//         std::cmp::max($x, max!($( $y ),+))
//     }
// }
// #[macro_export]
// macro_rules! min {
//     ($x: expr) => ($x);
//     ($x: expr, $( $y: expr ),+) => {
//         std::cmp::min($x, min!($( $y ),+))
//     }
// }
// #[derive(Debug, Clone)]
// struct UnionFind {
//     parent: Vec<isize>,
//     size: usize,
// }
// impl UnionFind {
//     fn new(n: usize) -> Self {
//         UnionFind {
//             parent: vec![-1; n + 1],
//             size: n,
//         }
//     }
//     fn find(&mut self, x: usize) -> usize {
//         if self.parent[x] < 0 {
//             return x;
//         }
//         let root = self.find(self.parent[x] as usize);
//         self.parent[x] = root as isize;
//         root
//     }
//     fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
//         let root_x = self.find(x);
//         let root_y = self.find(y);
//         if root_x == root_y {
//             return None;
//         }
//         let size_x = -self.parent[root_x];
//         let size_y = -self.parent[root_y];
//         self.size -= 1;
//         if size_x >= size_y {
//             self.parent[root_x] -= size_y;
//             self.parent[root_y] = root_x as isize;
//             Some((root_x, root_y))
//         } else {
//             self.parent[root_y] -= size_x;
//             self.parent[root_x] = root_y as isize;
//             Some((root_y, root_x))
//         }
//     }
//     fn is_same(&mut self, x: usize, y: usize) -> bool {
//         self.find(x) == self.find(y)
//     }
//     fn is_root(&mut self, x: usize) -> bool {
//         self.find(x) == x
//     }
//     fn get_union_size(&mut self, x: usize) -> usize {
//         let root = self.find(x);
//         -self.parent[root] as usize
//     }
//     fn get_size(&self) -> usize {
//         self.size
//     }
// }
// #[derive(Default)]
// struct Solver {}
// impl Solver {
//     fn solve(&mut self) {
//         let N = read::<usize>().unwrap();
//         let mut G = vec![vec![]; N];
//         for _ in 0..N - 1 {
//             let vec = read_vec::<usize>().unwrap();
//             let a = vec[0];
//             let b = vec[1];
//             G[a].push(b);
//             G[b].push(a);
//         }

//         let mut visited = vec![false; N];
//         let mut parents = vec![-1; N];
//         let mut children = vec![vec![]; N];
//         let mut Q = VecDeque::new();
//         let root = 0;
//         Q.push_back(root);
//         visited[root] = true;
//         while !Q.is_empty() {
//             let pos = Q.pop_front().unwrap();
//             for &next in &G[pos] {
//                 if !visited[next] {
//                     visited[next] = true;
//                     parents[next] = pos as isize;
//                     children[pos].push(next);
//                     Q.push_back(next);
//                 }
//             }
//         }

//         let mut visited = vec![false; N];
//         let mut is_chosen = vec![false; N];
//         visited[root] = true;
//         let mut ans = 0_usize;
//         dfs(root, &G, &children, &mut visited, &mut is_chosen, &mut ans);

//         print!("{}", ans);
//     }
// }
// fn main() {
//     std::thread::Builder::new()
//         .stack_size(128 * 1024 * 1024)
//         .spawn(|| Solver::default().solve())
//         .unwrap()
//         .join()
//         .unwrap();
// }

// fn dfs(
//     pos: usize,
//     G: &Vec<Vec<usize>>,
//     children: &Vec<Vec<usize>>,
//     visited: &mut Vec<bool>,
//     is_chosen: &mut Vec<bool>,
//     ans: &mut usize,
// ) {
//     for &next in &G[pos] {
//         if !visited[next] {
//             visited[next] = true;
//             dfs(next, G, children, visited, is_chosen, ans);
//         }
//     }

//     let mut ok = false;
//     for &c in &children[pos] {
//         ok |= !is_chosen[c];
//     }
//     if ok {
//         *ans += 1;
//         is_chosen[pos] = true;
//         for &c in &children[pos] {
//             is_chosen[c] = true;
//         }
//     }
// }

// fn eratosthenes(n: usize) -> Vec<bool> {
//     let mut is_prime_list = vec![true; n + 1];
//     is_prime_list[0] = false;
//     is_prime_list[1] = false;
//     let mut i = 2;
//     while i * i <= n {
//         if is_prime_list[i] {
//             let mut j = i * i;
//             while j <= n {
//                 is_prime_list[j] = false;
//                 j += i;
//             }
//         }
//         i += 1
//     }
//     is_prime_list
// }

// fn mod_pow(a: usize, b: usize, m: usize) -> usize {
//     let mut p = a;
//     let mut ret = 1;
//     let mut n = b;
//     while n > 0 {
//         if n & 1 == 1 {
//             ret = ret * p % m;
//         }
//         p = p * p % m;
//         n >>= 1;
//     }
//     ret
// }

// fn mod_div(a: usize, b: usize, m: usize) -> usize {
//     (a * mod_pow(b, m - 2, m)) % m
// }

// fn prime_factorize(n: usize) -> BTreeMap<usize, usize> {
//     let mut nn = n;
//     let mut i = 2;
//     let mut pf: BTreeMap<usize, usize> = BTreeMap::new();
//     while i * i <= n {
//         while nn % i == 0 {
//             *pf.entry(i).or_default() += 1;
//             nn /= i;
//         }
//         i += 1;
//     }
//     if nn != 1 {
//         *pf.entry(nn).or_default() += 1;
//     }
//     pf
// }

// fn enum_dividers(n: usize) -> Vec<usize> {
//     let mut i = 1_usize;
//     let mut ret = vec![];
//     while i * i <= n {
//         if n % i == 0 {
//             ret.push(i);
//             if i != n / i {
//                 ret.push(n / i);
//             }
//         }
//         i += 1;
//     }
//     ret.sort();
//     ret
// }

#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
use std::collections::BTreeMap;
use std::ops;

use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

const MOD: usize = 1e9 as usize + 7;
// const MOD: usize = 998244353;
// const MOD: usize = 2147483647;

#[macro_export]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $( $y: expr ),+) => {
        std::cmp::max($x, max!($( $y ),+))
    }
}
#[macro_export]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $( $y: expr ),+) => {
        std::cmp::min($x, min!($( $y ),+))
    }
}

#[derive(Debug, Clone)]
struct UnionFind {
    parent: Vec<isize>,
    size: usize,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            parent: vec![-1; n],
            size: n,
        }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] < 0 {
            return x;
        }
        let root = self.find(self.parent[x] as usize);
        self.parent[x] = root as isize;
        root
    }
    fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
        let root_x = self.find(x);
        let root_y = self.find(y);
        if root_x == root_y {
            return None;
        }
        let size_x = -self.parent[root_x];
        let size_y = -self.parent[root_y];
        self.size -= 1;
        if size_x >= size_y {
            self.parent[root_x] -= size_y;
            self.parent[root_y] = root_x as isize;
            Some((root_x, root_y))
        } else {
            self.parent[root_y] -= size_x;
            self.parent[root_x] = root_y as isize;
            Some((root_y, root_x))
        }
    }
    fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
    fn is_root(&mut self, x: usize) -> bool {
        self.find(x) == x
    }
    fn get_union_size(&mut self, x: usize) -> usize {
        let root = self.find(x);
        -self.parent[root] as usize
    }
    fn get_size(&self) -> usize {
        self.size
    }
    fn roots(&self) -> Vec<usize> {
        (0..self.parent.len())
            .filter(|i| self.parent[*i] < 0)
            .collect::<Vec<usize>>()
    }
    fn members(&mut self, x: usize) -> Vec<usize> {
        let root = self.find(x);
        (0..self.parent.len())
            .filter(|i| self.find(*i) == root)
            .collect::<Vec<usize>>()
    }
    fn all_group_members(&mut self) -> BTreeMap<usize, Vec<usize>> {
        let mut groups_map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
        for x in 0..self.parent.len() {
            let r = self.find(x);
            groups_map.entry(r).or_default().push(x);
        }
        groups_map
    }
}

type M = ModInt;
#[derive(Debug, Clone, Copy)]
struct ModInt {
    value: usize,
}

impl ModInt {
    fn new(n: usize) -> Self {
        ModInt { value: n % MOD }
    }
    fn zero() -> Self {
        ModInt { value: 0 }
    }
    fn one() -> Self {
        ModInt { value: 1 }
    }
    fn value(&self) -> usize {
        self.value
    }
    fn pow(&self, n: usize) -> Self {
        let mut p = *self;
        let mut ret = ModInt::one();
        let mut nn = n;
        while nn > 0 {
            if nn & 1 == 1 {
                ret *= p;
            }
            p *= p;
            nn >>= 1;
        }
        ret
    }
    fn inv(&self) -> Self {
        ModInt::new((ext_gcd(self.value, MOD).0 + MOD as isize) as usize)
    }
}

impl ops::Add for ModInt {
    type Output = ModInt;
    fn add(self, other: Self) -> Self {
        ModInt::new(self.value + other.value)
    }
}

impl ops::Sub for ModInt {
    type Output = ModInt;
    fn sub(self, other: Self) -> Self {
        ModInt::new(MOD + self.value - other.value)
    }
}

impl ops::Mul for ModInt {
    type Output = ModInt;
    fn mul(self, other: Self) -> Self {
        ModInt::new(self.value * other.value)
    }
}

#[allow(clippy::suspicious_arithmetic_impl)]
impl ops::Div for ModInt {
    type Output = ModInt;
    fn div(self, other: Self) -> Self {
        self * other.inv()
    }
}

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

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

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

impl ops::DivAssign for ModInt {
    fn div_assign(&mut self, other: Self) {
        *self = *self / other;
    }
}

#[derive(Debug, Clone)]
struct Comb {
    fact: Vec<ModInt>,
    fact_inverse: Vec<ModInt>,
}

impl Comb {
    fn new(n: usize) -> Self {
        let mut fact = vec![M::one(), M::one()];
        let mut fact_inverse = vec![M::one(), M::one()];
        let mut inverse = vec![M::zero(), M::one()];
        for i in 2..=n {
            fact.push(*fact.last().unwrap() * M::new(i));
            inverse.push((M::zero() - inverse[MOD % i]) * M::new(MOD / i));
            fact_inverse.push(*fact_inverse.last().unwrap() * *inverse.last().unwrap());
        }
        Comb { fact, fact_inverse }
    }
    fn nCr(&self, n: usize, r: usize) -> ModInt {
        self.fact[n] * self.fact_inverse[n - r] * self.fact_inverse[r]
    }
    fn nHr(&self, n: usize, r: usize) -> ModInt {
        self.nCr(n + r - 1, r)
    }
}

#[derive(Default)]
struct Solver {}
impl Solver {
    #[fastout]
    fn solve(&mut self) {
        input! {
            A: isize,
            B: isize
        }
        let mut D = (A - B).abs();
        let mut C = A + B - D;
        let mut ans = (C - D).abs();
        while C >= 2 {
            C -= 2;
            D += 2;
            ans = min!(ans, (C - D).abs());
        }
        println!("{}", ans);
    }
}

fn main() {
    std::thread::Builder::new()
        .stack_size(128 * 1024 * 1024)
        .spawn(|| Solver::default().solve())
        .unwrap()
        .join()
        .unwrap();
}

fn eratosthenes(n: usize) -> Vec<bool> {
    let mut is_prime_list = vec![true; n + 1];
    is_prime_list[0] = false;
    is_prime_list[1] = false;
    let mut i = 2;
    while i * i <= n {
        if is_prime_list[i] {
            let mut j = i * i;
            while j <= n {
                is_prime_list[j] = false;
                j += i;
            }
        }
        i += 1
    }
    is_prime_list
}

fn legendre(n: usize, p: usize) -> usize {
    let mut cnt = 0_usize;
    let mut pp = p;
    while pp <= n {
        cnt += n / pp;
        pp *= p;
    }
    cnt
}

fn mod_pow(a: usize, b: usize) -> usize {
    let mut p = a;
    let mut ret = 1;
    let mut n = b;
    while n > 0 {
        if n & 1 == 1 {
            ret = ret * p % MOD;
        }
        p = p * p % MOD;
        n >>= 1;
    }
    ret
}

fn mod_pow2(a: usize, b: usize, m: usize) -> usize {
    let mut p = a;
    let mut ret = 1;
    let mut n = b;
    while n > 0 {
        if n & 1 == 1 {
            ret = ret * p % m;
        }
        p = p * p % m;
        n >>= 1;
    }
    ret
}

fn mod_inv(a: usize, b: usize) -> usize {
    (a * mod_pow(b, MOD - 2)) % MOD
}

fn prime_factorize(n: usize) -> BTreeMap<usize, usize> {
    let mut nn = n;
    let mut i = 2;
    let mut pf: BTreeMap<usize, usize> = BTreeMap::new();
    while i * i <= n {
        while nn % i == 0 {
            *pf.entry(i).or_default() += 1;
            nn /= i;
        }
        i += 1;
    }
    if nn != 1 {
        *pf.entry(nn).or_default() += 1;
    }
    pf
}

fn enum_dividers(n: usize) -> Vec<usize> {
    let mut i = 1_usize;
    let mut ret = vec![];
    while i * i <= n {
        if n % i == 0 {
            ret.push(i);
            if i != n / i {
                ret.push(n / i);
            }
        }
        i += 1;
    }
    ret.sort();
    ret
}

// ax+by=gcd(a, b)
fn ext_gcd(a: usize, b: usize) -> (isize, isize, usize) {
    if a == 0 {
        return (0, 1, b);
    }
    let (x, y, g) = ext_gcd(b % a, a);
    (y - b as isize / a as isize * x, x, g)
}

fn mod_inv2(x: usize) -> usize {
    (ext_gcd(x, MOD).0 + MOD as isize) as usize % MOD
}
yukicoder

結果

ソースコード
