MikuroXina

/// Calculates the inverse of square root quickly.
fn inv_sqrt(x: f64) -> f64 {
  // x must be positive.
  assert!(x.is_sign_positive());

  // mu := 0.045
  // log(x) ≒ x + mu
  // log(a) := log(1 / √x) = - 1/2 log(x)
  // 1/2^52 (a_man + 2^52 * a_exp) - 1023 + mu
  //  = - 1/2 (1/2^52 (x_man + 2^52 * x_exp) - 1023 + mu)

MikuroXina

use std::num::NonZeroUsize;

/// Calculates the lowest common ancestor on given graph.
#[derive(Debug)]
pub struct LowestCommonAncestor {
    parents_by_step: Vec<Vec<Option<NonZeroUsize>>>,
    distances: Vec<usize>,
}

impl LowestCommonAncestor {

MikuroXina

let alpha_num_pat = RegExp::pat()
  .with_alphabetic()
  .with_numeric();
let email_user_chars = RegExp::new().one_of(RegExp::pat().add(
  "!#$%&'*+/=?^_`{|}~-"
).with_alphabetic().with_numeric());
let email_num_chars = RegExp::new().or(
  RegExp::new().text("25").one_of(RegExp::pat().add('0'..='5')),
  RegExp::new().or(
    RegExp::new()

MikuroXina

use std::collections::HashMap;

fn sieve(max: usize) -> (Vec<usize>, HashMap<usize, usize>) {
    let mut found_primes = vec![];
    let mut found_least_factor = HashMap::with_capacity(max + 1);
    for n in 2..=max {
        let factor = *found_least_factor.entry(n).or_insert_with(|| {
            found_primes.push(n);
            n
        });

MikuroXina

/// It represents index of parent if positive, otherwise size of tree.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct UnionFindIndex(isize);

impl UnionFindIndex {
    fn new(index: usize) -> Self {
        debug_assert!(index < (isize::MAX as usize));
        Self(index as isize)
    }

MikuroXina

use num::{One, Zero};

/// An integer mod n.
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ModInt<const MOD: u64>(u64);

impl<const MOD: u64> ModInt<MOD> {
    pub fn as_u64(self) -> u64 {
        self.0
    }

MikuroXina

pub struct Digits {
    num: u64,
    radix: u64,
}

impl Digits {
    pub fn new(num: u64, radix: u64) -> Self {
        assert!(0 < radix, "radix must be greater than zero");
        Self { num, radix }
    }

MikuroXina

use std::{
  collections::BinaryHeap,
  ops::*,
};

struct SlopeTrick<T> {
  left: BinaryHeap<T>,
  right: BinaryHeap<T>,
  bias: T,
}

MikuroXina

/// A monoid with inverse and zero element.
pub trait InvZeroMonoid: From<u64> + Copy + Sized {
    /// for all x; x.op(ZERO) == ZERO
    const ZERO: Self;
    /// for all x; x.op(ONE) == x
    const ONE: Self;

    /// for all x, y, z; x.op(y).op(z) == x.op(y.op(z))
    fn op(self, rhs: Self) -> Self;
    /// for all x; if x != ZERO then x.op(x.inv()) == ONE

MikuroXina

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct ChebyshevPoint(i64, i64);

impl ChebyshevPoint {
    fn from_manhattan(x: i64, y: i64) -> Self {
        Self(x - y, x + y)
    }

    fn manhattan_dist(self, other: Self) -> u64 {
        self.0.abs_diff(other.0).max(self.1.abs_diff(other.1))