Skip to content

Instantly share code, notes, and snippets.

@Tosainu
Last active May 2, 2020 14:51
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Tosainu/eea8b05272d999534934c16c91caf6a3 to your computer and use it in GitHub Desktop.
Rust の競プロ用テンプレート
#![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]
}
}
}
#!/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