Rust の競プロ用テンプレート
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#![allow(unused_imports)] | |
use std::cmp::{max, min, Reverse}; | |
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; | |
use itertools::Itertools; | |
use nyan::*; | |
fn main() -> Result<(), Box<dyn std::error::Error>> { | |
let stdin = std::io::stdin(); | |
let mut sc = Scanner::new(stdin.lock()); | |
let a: u64 = sc.read()?; | |
let b: u64 = sc.read()?; | |
// let n: usize = sc.read()?; | |
// let a: Vec<u64> = sc.read_vec(n)?; | |
// let n: usize = sc.read()?; | |
// let p: Vec<(u64, u64)> = (0..n) | |
// .map(|_| { | |
// let ai = sc.read()?; | |
// let bi = sc.read()?; | |
// Ok((ai, bi)) | |
// }) | |
// .collect::<Result<_, Box<dyn std::error::Error>>>()?; | |
// let _n: usize = sc.read()?; | |
// let s: Vec<_> = sc.read_line()?; | |
let mut ans = a + b; | |
println!("{}", ans); | |
// if true { | |
// println!("Yes"); | |
// } else { | |
// println!("No"); | |
// } | |
// println!("{}", ans.iter().format(" ")); | |
Ok(()) | |
} | |
#[allow(dead_code)] | |
mod nyan { | |
use std::error::Error; | |
use std::fmt::{Debug, Display}; | |
use std::io; | |
use std::iter::FromIterator; | |
use std::str::FromStr; | |
pub struct Scanner<R: io::BufRead> { | |
reader: R, | |
buffer: String, | |
cursor: usize, | |
} | |
impl<R: io::BufRead> Scanner<R> { | |
pub fn new(reader: R) -> Scanner<R> { | |
Scanner { | |
reader, | |
buffer: String::with_capacity(32), | |
cursor: 0, | |
} | |
} | |
fn next<F: Fn(char) -> bool>(&mut self, f: F) -> io::Result<&str> { | |
loop { | |
if let Some(l) = self.buffer[self.cursor..].find(|c: char| !c.is_ascii_whitespace()) | |
{ | |
self.cursor += l; | |
break; | |
} | |
self.buffer.clear(); | |
self.cursor = 0; | |
match self.reader.read_line(&mut self.buffer) { | |
Err(e) => return Err(e), | |
Ok(0) => return Err(io::Error::from(io::ErrorKind::UnexpectedEof)), | |
_ => (), | |
} | |
} | |
let start = self.cursor; | |
self.cursor = self.buffer[start..] | |
.find(f) | |
.map_or(self.buffer.len(), |l| start + l); | |
Ok(&self.buffer[start..self.cursor]) | |
} | |
fn next_word(&mut self) -> io::Result<&str> { | |
self.next(|c| c.is_ascii_whitespace()) | |
} | |
fn next_line(&mut self) -> io::Result<&str> { | |
self.next(|c| c == '\n' || c == '\r') | |
} | |
pub fn read<T>(&mut self) -> Result<T, Box<dyn Error>> | |
where | |
T: FromStr, | |
T::Err: 'static + Error, | |
{ | |
Ok(self.next_word()?.parse()?) | |
} | |
pub fn read_vec<T, U>(&mut self, n: usize) -> Result<T, Box<dyn Error>> | |
where | |
T: FromIterator<U>, | |
U: FromStr, | |
U::Err: 'static + Error, | |
{ | |
(0..n).map(|_| self.read()).collect() | |
} | |
pub fn read_vec2d<T, U, V>(&mut self, m: usize, n: usize) -> Result<T, Box<dyn Error>> | |
where | |
T: FromIterator<U>, | |
U: FromIterator<V>, | |
V: FromStr, | |
V::Err: 'static + Error, | |
{ | |
(0..m).map(|_| self.read_vec(n)).collect() | |
} | |
pub fn read_line<T: FromIterator<char>>(&mut self) -> io::Result<T> { | |
self.next_line().map(|l| l.chars().collect()) | |
} | |
pub fn read_lines<T, U>(&mut self, n: usize) -> io::Result<T> | |
where | |
T: FromIterator<U>, | |
U: FromIterator<char>, | |
{ | |
(0..n).map(|_| self.read_line()).collect() | |
} | |
} | |
#[test] | |
fn test_scanner_next_word() { | |
let buf = io::Cursor::new(b"hello world\nfoo\n\n\n\nbar\n"); | |
let mut r = Scanner::new(buf); | |
assert_eq!(r.next_word().unwrap(), "hello"); | |
assert_eq!(r.next_word().unwrap(), "world"); | |
assert_eq!(r.next_word().unwrap(), "foo"); | |
assert_eq!(r.next_word().unwrap(), "bar"); | |
assert!(r.next_word().is_err()); | |
assert!(r.next_word().is_err()); | |
} | |
#[test] | |
fn test_scanner_next_line() { | |
let buf = io::Cursor::new(b"hello world\nfoo\n\n\n\nbar\n"); | |
let mut r = Scanner::new(buf); | |
assert_eq!(r.next_line().unwrap(), "hello world"); | |
assert_eq!(r.next_line().unwrap(), "foo"); | |
assert_eq!(r.next_line().unwrap(), "bar"); | |
assert!(r.next_line().is_err()); | |
assert!(r.next_line().is_err()); | |
} | |
#[test] | |
fn test_scanner_no_linebreak() { | |
let buf = io::Cursor::new(b"hello world"); | |
let mut r = Scanner::new(buf); | |
assert_eq!(r.next_word().unwrap(), "hello"); | |
assert_eq!(r.next_word().unwrap(), "world"); | |
assert!(r.next_word().is_err()); | |
assert!(r.next_word().is_err()); | |
} | |
// C++ like binary search functions (upper_bound, lower_bound, equal_range) | |
pub trait BinarySearch<T> { | |
fn lower_bound(&self, value: &T) -> usize; | |
fn upper_bound(&self, value: &T) -> usize; | |
fn equal_range(&self, value: &T) -> (usize, usize) { | |
(self.lower_bound(value), self.upper_bound(value)) | |
} | |
} | |
impl<T: Ord> BinarySearch<T> for [T] { | |
// https://en.cppreference.com/w/cpp/algorithm/lower_bound#Possible_implementation | |
fn lower_bound(&self, value: &T) -> usize { | |
let mut first = 0; | |
let mut last = self.len(); | |
while last != first { | |
let mid = (first + last) / 2; | |
if self[mid] < *value { | |
first = mid + 1; | |
} else { | |
last = mid; | |
} | |
} | |
first | |
} | |
// https://en.cppreference.com/w/cpp/algorithm/upper_bound#Possible_implementation | |
fn upper_bound(&self, value: &T) -> usize { | |
let mut first = 0; | |
let mut last = self.len(); | |
while last != first { | |
let mid = (first + last) / 2; | |
if self[mid] > *value { | |
last = mid; | |
} else { | |
first = mid + 1; | |
} | |
} | |
first | |
} | |
} | |
#[test] | |
pub fn test_binary_search() { | |
let data = vec![1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6]; | |
assert_eq!(data.lower_bound(&4), 7); | |
assert_eq!(data.upper_bound(&4), 10); | |
} | |
// Extended Euclidean algorithm | |
// ax + by = gcd(x, y) | |
pub fn extended_gcd(a: u64, b: u64) -> (u64, i64, i64) { | |
if b == 0 { | |
(a, 1, 0) | |
} else { | |
let (m, y, x) = extended_gcd(b, a % b); | |
(m, x, y - (a / b) as i64 * x) | |
} | |
} | |
pub fn gcd(a: u64, b: u64) -> u64 { | |
if b == 0 { | |
a | |
} else { | |
gcd(b, a % b) | |
} | |
} | |
pub fn lcm(a: u64, b: u64) -> u64 { | |
a / gcd(a, b) * b | |
} | |
// x^n (mod p) | |
pub fn pow_mod(mut x: u64, mut n: u64, p: u64) -> u64 { | |
let mut r = 1; | |
while n > 0 { | |
if n & 1 > 0 { | |
r = (r * x) % p; | |
} | |
x = (x * x) % p; | |
n >>= 1; | |
} | |
r | |
} | |
#[test] | |
fn test_pow_mod() { | |
assert_eq!(pow_mod(4, 13, 497), 445); | |
assert_eq!(pow_mod(2, 90, 13), 12); | |
assert_eq!(pow_mod(2, 99999999, 147), 134); | |
} | |
// a^{p-1} = 1 (mod p) (Fermat's little theorem) | |
// a^{p - 2} * a = 1 → a^{-1} = a^{p-2} | |
pub fn inv_mod(n: u64, p: u64) -> u64 { | |
pow_mod(n, p - 2, p) | |
} | |
// s * (s + 1) * .. * t (mod p) | |
pub fn prod_mod(s: u64, t: u64, p: u64) -> u64 { | |
(s..=t).fold(1, |acc, x| acc * x % p) | |
} | |
// nCk (mod p) | |
pub fn comb_mod(n: u64, k: u64, p: u64) -> u64 { | |
// nCk = n! / (k! * (n - k)!) | |
// = ((n-k+1) * (n-k+2) * ... * n) * inv(k!) | |
prod_mod(n - k + 1, n, p) * inv_mod(prod_mod(1, k, p), p) % p | |
} | |
// comb_mod_multi(n_max, p)(n, k) = nCk (mod p) | |
pub fn comb_mod_multi(n_max: u64, p: u64) -> impl Fn(u64, u64) -> u64 { | |
// fact[n] = n!, fact_inv[n] = (n!)^(-1) (mod p) | |
let fact = std::iter::once(1) | |
.chain(1..=n_max) | |
.scan(1, |state, x| { | |
*state = (*state * x) % p; | |
Some(*state) | |
}) | |
.collect::<Vec<_>>(); | |
let fact_inv = fact.iter().map(|&x| inv_mod(x, p)).collect::<Vec<_>>(); | |
move |n, k| { | |
let a = fact[n as usize]; | |
let b = fact_inv[k as usize]; | |
let c = fact_inv[(n - k) as usize]; | |
(((a * b) % p) * c) % p | |
} | |
} | |
#[inline] | |
pub fn minmax<T: Ord>(a: T, b: T) -> (T, T) { | |
if a < b { | |
(a, b) | |
} else { | |
(b, a) | |
} | |
} | |
#[test] | |
fn test_minmax() { | |
assert_eq!(minmax(1, 3), (1, 3)); | |
assert_eq!(minmax(3, 1), (1, 3)); | |
} | |
#[inline] | |
pub fn digits(x: u64, base: u64) -> u32 { | |
(1..) | |
.find(|&i| base.pow(i - 1) <= x && x < base.pow(i)) | |
.unwrap_or(0) | |
} | |
#[test] | |
fn test_digits() { | |
assert_eq!(digits(1234, 10), 4); | |
assert_eq!(digits(1234567890, 10), 10); | |
assert_eq!(digits(0xdeadbeef, 16), 8); | |
assert_eq!(digits(0o123456, 8), 6); | |
assert_eq!(digits(0b10101, 2), 5); | |
} | |
pub struct UnionFind { | |
n: usize, | |
root: Vec<usize>, | |
rank: Vec<usize>, | |
size: Vec<usize>, | |
} | |
impl UnionFind { | |
pub fn new(n: usize) -> UnionFind { | |
UnionFind { | |
n, | |
root: (0..n).collect(), | |
rank: vec![0; n], | |
size: vec![1; n], | |
} | |
} | |
pub fn root(&mut self, x: usize) -> usize { | |
let r = self.root[x]; | |
if r == x { | |
r | |
} else { | |
self.root[x] = self.root(r); | |
self.root[x] | |
} | |
} | |
pub fn merge(&mut self, x: usize, y: usize) { | |
let rx = self.root(x); | |
let ry = self.root(y); | |
if rx == ry { | |
return; | |
} | |
if self.rank[rx] < self.rank[ry] { | |
self.root[rx] = ry; | |
self.size[ry] += self.size[rx]; | |
} else { | |
self.root[ry] = rx; | |
self.size[rx] += self.size[ry]; | |
if self.rank[rx] == self.rank[ry] { | |
self.rank[rx] += 1; | |
} | |
} | |
} | |
pub fn size(&mut self, x: usize) -> usize { | |
let rx = self.root(x); | |
self.size[rx] | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/bin/bash -e | |
if [ $# -ne 1 ]; then | |
echo "usage: $0 <contest name>" >&2 | |
exit 1 | |
fi | |
scriptdir=$(dirname "$0") | |
project_name=$1 | |
if [ -d "$project_name" ]; then | |
echo "'$project_name' exists" >&2 | |
exit 1 | |
fi | |
mkdir "$project_name" | |
cat > "${project_name}/Cargo.toml" <<EOS | |
[package] | |
name = "${project_name}" | |
version = "1.0.0" | |
edition = "2018" | |
EOS | |
for p in {a,b,c,d,e,f}; do | |
cp -i "${scriptdir}/a.rs" "${project_name}/${p}.rs" | |
cat >> "${project_name}/Cargo.toml" <<EOS | |
[[bin]] | |
name = "${p}" | |
path = "${p}.rs" | |
EOS | |
done | |
cat >> "${project_name}/Cargo.toml" <<EOS | |
[dependencies] | |
itertools = "0.9.0" | |
lazy_static = "1.4.0" | |
num-complex = "0.2.4" | |
num-traits = "0.2.11" | |
rand = { version = "0.7.3", features = ["small_rng"] } | |
regex = "1.3.6" | |
EOS |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment