結果
問題 | No.1057 素敵な日 |
ユーザー |
|
提出日時 | 2020-06-22 22:13:22 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 24,166 bytes |
コンパイル時間 | 11,864 ms |
コンパイル使用メモリ | 401,304 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-03 18:55:28 |
合計ジャッジ時間 | 12,640 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 |
コンパイルメッセージ
warning: unused import: `self::matrix::Matrix` --> src/main.rs:2:5 | 2 | use self::matrix::Matrix; | ^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `self::mod_int::ModInt` --> src/main.rs:3:5 | 3 | use self::mod_int::ModInt; | ^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::f64::consts::PI` --> src/main.rs:6:5 | 6 | use std::f64::consts::PI; | ^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::str::*` --> src/main.rs:8:5 | 8 | use std::str::*; | ^^^^^^^^^^^ warning: unused macro definition: `min` --> src/main.rs:65:14 | 65 | macro_rules! min { | ^^^ | = note: `#[warn(unused_macros)]` on by default warning: unused macro definition: `chmin` --> src/main.rs:77:14 | 77 | macro_rules! chmin { | ^^^^^ warning: unused macro definition: `max` --> src/main.rs:89:14 | 89 | macro_rules! max { | ^^^ warning: unused macro definition: `chmax` --> src/main.rs:101:14 | 101 | macro_rules! chmax { | ^^^^^ warning: the item `Write` is imported redundantly --> src/main.rs:136:13 | 7 | use std::io::*; | ---------- the item `Write` is already imported here ... 136 | use std::io::Write; | ^^^^^^^^^^^^^^ warning: the item `Read` is imported redundantly --> src/main.rs:141:13 | 7 | use std::io::*; | ---------- the item `Read` is already imported here ... 141 | use std::io::Read; | ^^^^^^^^^^^^^ warning: the item `BinaryHeap` is imported redundantly --> src/main.rs:266:9 | 5 | use std::collections::*; | ------------------- the item `BinaryHeap` is already imported here ... 266 | use std::collections::BinaryHeap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unnecessary parentheses around assigned value --> src/main.rs:988:23 | 988 | let mid = ((ok + ng) / 2); |
ソースコード
use self::algebra::*;use self::matrix::Matrix;use self::mod_int::ModInt;use std::cmp::*;use std::collections::*;use std::f64::consts::PI;use std::io::*;use std::str::*;use std::string::*;macro_rules! read {(($($t:tt),*)) => {( $(read!($t)),* )};([[$t:tt; $len1:expr]; $len2:expr]) => {(0..$len2).map(|_| read!([$t; $len1])).collect::<Vec<_>>()};([$t:tt; $len:expr]) => {(0..$len).map(|_| read!($t)).collect::<Vec<_>>()};(chars) => {read!(String).chars().collect::<Vec<char>>()};(usize1) => {read!(usize) - 1};($t:ty) => {{let stdin = stdin();let stdin = stdin.lock();let token: String = stdin.bytes().map(|c| c.unwrap() as char).skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace()).collect();token.parse::<$t>().unwrap()}};}macro_rules! input {(mut $name:ident: $t:tt, $($r:tt)*) => {let mut $name = read!($t);input!($($r)*);};(mut $name:ident: $t:tt) => {let mut $name = read!($t);};($name:ident: $t:tt, $($r:tt)*) => {let $name = read!($t);input!($($r)*);};($name:ident: $t:tt) => {let $name = read!($t);};}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! chmin {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_min = min!($($cmps),+);if $base > cmp_min {$base = cmp_min;true} else {false}}};}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),+))}};}macro_rules! chmax {($base:expr, $($cmps:expr),+ $(,)*) => {{let cmp_max = max!($($cmps),+);if $base < cmp_max {$base = cmp_max;true} else {false}}};}#[derive(Eq, PartialEq, Clone, Debug)]pub struct Rev<T>(pub T);impl<T: PartialOrd> PartialOrd for Rev<T> {fn partial_cmp(&self, other: &Rev<T>) -> Option<std::cmp::Ordering> {other.0.partial_cmp(&self.0)}}impl<T: Ord> Ord for Rev<T> {fn cmp(&self, other: &Rev<T>) -> std::cmp::Ordering {other.0.cmp(&self.0)}}struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);impl<R: std::io::Read, W: std::io::Write> IO<R, W> {pub fn new(r: R, w: W) -> Self {IO(r, std::io::BufWriter::new(w))}pub fn write<S: ToString>(&mut self, s: S) {use std::io::Write;self.1.write(s.to_string().as_bytes()).unwrap();}pub fn read<T: std::str::FromStr>(&mut self) -> T {use std::io::Read;let s: String = self.0.by_ref().bytes().map(|b| b.unwrap() as char).skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace()).collect();return s.parse::<T>().ok().unwrap();}pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {(0..n).map(|_| self.read()).collect()}pub fn chars(&mut self) -> Vec<char> {self.read::<String>().chars().collect()}}fn prime_factorization(n: i64) -> HashMap<i64, i64> {let mut n = n;let mut res = HashMap::new();let mut i = 2;while i * i <= n {while n % i == 0 {n /= i;let count = res.entry(i).or_insert(0);*count += 1;}i += 1;}if n > 1 {res.insert(n, 1);}return res;}struct Combination {MOD: i64,fac: Vec<i64>,fac_inv: Vec<i64>,}impl Combination {pub fn new(n: i64) -> Self {let MOD: i64 = 1_000_000_007;let mut fac: Vec<i64> = vec![0; n as usize + 1];let mut fac_inv: Vec<i64> = vec![0; n as usize + 1];let get_inverse = |mut n: i64| -> i64 {let (mut res, mut p) = (1, MOD - 2);while p != 0 {if p & 1 == 1 {res = (res * n) % MOD;}n = (n * n) % MOD;p >>= 1;}return res;};fac[0] = 1;for i in 1..n + 1 {fac[i as usize] = (fac[i as usize - 1] * i) % MOD;}for i in 0..n + 1 {fac_inv[i as usize] = get_inverse(fac[i as usize]);}Combination {MOD: MOD,fac: fac,fac_inv: fac_inv,}}fn nCr(&self, n: i64, r: i64) -> i64 {if n < r {return 0;}let a: i64 = self.fac[n as usize];let b: i64 = self.fac_inv[(n - r) as usize];let c: i64 = self.fac_inv[r as usize];let bc: i64 = (b * c) % self.MOD;return (a * bc) % self.MOD;}fn nPr(&self, n: i64, r: i64) -> i64 {if n < r {return 0;}let a: i64 = self.fac[n as usize];let b: i64 = self.fac_inv[(n - r) as usize];return (a * b) % self.MOD;}fn nHr(&self, n: i64, r: i64) -> i64 {if n == 0 && r == 0 {return 1;}return self.nCr(n + r - 1, r);}}#[derive(Copy, Clone, Eq, PartialEq)]struct Edge {to: usize,cost: i64,}fn dijkstra(graph: &Vec<Vec<Edge>>, s: &usize) -> Vec<i64> {use std::collections::BinaryHeap;let mut dist = vec![1e18 as i64; graph.len()];let mut heap = BinaryHeap::new();dist[*s] = 0;heap.push(Rev((0, *s)));while let Some(Rev((cost, v))) = heap.pop() {if dist[v] < cost {continue;}for e in &graph[v] {if dist[e.to] <= dist[v] + e.cost {continue;}dist[e.to] = dist[v] + e.cost;heap.push(Rev((dist[e.to], e.to)));}}return dist;}struct LCA {par: Vec<Vec<Option<usize>>>,dist: Vec<i64>,}impl LCA {pub fn new(graph: &Vec<Vec<usize>>, root: usize) -> LCA {let V = graph.len();let mut K = 1;while (1 << K) < V {K += 1;}let mut par = vec![vec![None; V]; K];let mut dist = vec![-1; V];let graph = graph.to_vec();fn dfs(v: usize,p: Option<usize>,d: i64,graph: &Vec<Vec<usize>>,par: &mut Vec<Vec<Option<usize>>>,dist: &mut Vec<i64>,) {par[0][v] = p;dist[v] = d;for &to in &graph[v] {match p {Some(p) => {if to != p {dfs(to, Some(v), d + 1, graph, par, dist)}}None => dfs(to, Some(v), d + 1, graph, par, dist),}}}dfs(root, None, 0, &graph, &mut par, &mut dist);for k in 0..K - 1 {for v in 0..V {match par[k][v] {Some(x) => par[k + 1][v] = par[k][x],None => (),}}}LCA {par: par,dist: dist,}}pub fn query(&self, u: usize, v: usize) -> usize {let mut u = u;let mut v = v;if self.dist[u] < self.dist[v] {return self.query(v, u);}let K = self.par.len();for k in 0..K {if ((self.dist[u] - self.dist[v]) >> k & 1) == 1 {u = self.par[k][u].unwrap();}}if u == v {return u;}for k in (0..K - 1).rev() {if self.par[k][u] != self.par[k][v] {u = self.par[k][u].unwrap();v = self.par[k][v].unwrap();}}return self.par[0][u].unwrap();}}struct Doubling {N: usize,LOG: usize,next: Vec<Vec<Option<usize>>>,}impl Doubling {pub fn new(vec: &Vec<usize>, lim: &usize) -> Doubling {let N = vec.len();let lim = *lim;let mut LOG = 1;while (1 << LOG) < 2 * lim {LOG += 1;}let mut next = vec![vec![None; N]; LOG];for i in 0..N {next[0][i] = Some(vec[i]);}for k in 0..LOG - 1 {for i in 0..N {match next[k][i] {Some(x) => next[k + 1][i] = next[k][x],None => (),}}}Doubling {N: N,LOG: LOG,next: next,}}pub fn query(&self, i: usize, n: usize) -> usize {let mut i = i;for k in (0..self.LOG).rev() {if (n >> k) & 1 == 1 {i = self.next[k][i].unwrap();}}return i;}}struct UnionFind {par: Vec<i32>,}impl UnionFind {pub fn new(n: usize) -> UnionFind {UnionFind { par: vec![-1; n] }}pub fn root(&mut self, x: usize) -> usize {if self.par[x] < 0 {return x;} else {let a = self.par[x] as usize;self.par[x] = self.root(a) as i32;return self.par[x] as usize;}}pub fn same(&mut self, x: usize, y: usize) -> bool {self.root(x) == self.root(y)}pub fn merge(&mut self, x: usize, y: usize) -> bool {let mut x = self.root(x);let mut y = self.root(y);if x == y {return false;} else {if self.par[x] > self.par[y] {std::mem::swap(&mut x, &mut y);}self.par[x] += self.par[y];self.par[y] = x as i32;return true;}}pub fn size(&mut self, x: usize) -> i64 {let a = self.root(x);return -self.par[a] as i64;}}pub mod algebra {pub trait Monoid {fn id() -> Self;fn op(&self, rhs: &Self) -> Self;}#[derive(Clone, Debug)]pub struct Min(i64);#[derive(Clone, Debug)]pub struct RangeUpdate(i64);#[derive(Clone, Debug)]pub struct RangeAdd(i64);#[derive(Clone, Debug)]pub struct Sum(i64);impl Monoid for Sum {fn id() -> Self {Sum(0)}fn op(&self, rhs: &Self) -> Self {Sum(self.0 + rhs.0)}}impl Monoid for Min {fn id() -> Self {Min(std::i32::MAX as i64)}fn op(&self, rhs: &Self) -> Self {Min(std::cmp::min(self.0, (*rhs).0))}}pub trait Operator {type T;fn id() -> Self;fn op(&self, rhs: &Self) -> Self;fn act(&self, tar: &Self::T, x: usize) -> Self::T;}impl Operator for RangeUpdate {type T = Min;fn id() -> Self {RangeUpdate(0)}fn op(&self, rhs: &Self) -> Self {(*rhs).clone()}fn act(&self, tar: &Self::T, x: usize) -> Self::T {Min(self.0)}}impl Operator for RangeAdd {type T = Sum;fn id() -> Self {RangeAdd(0)}fn op(&self, rhs: &Self) -> Self {RangeAdd(self.0 + rhs.0)}// Sum(tar.0 + self.0 * x as i64)fn act(&self, tar: &Self::T, x: usize) -> Self::T {Sum(tar.0 + self.0 * x as i64)}}pub trait Zero {fn zero() -> Self;}impl Zero for usize {fn zero() -> Self {0usize}}pub trait One {fn one() -> Self;}impl One for usize {fn one() -> Self {1usize}}}struct LazySegTree<M: Monoid, O: Operator<T = M>> {dat: Vec<M>,lzy: Vec<O>,need_update: Vec<bool>,size: usize,}impl<M: Monoid + Clone, O: Operator<T = M> + Clone> LazySegTree<M, O> {pub fn new(vec: Vec<M>) -> LazySegTree<M, O> {let n = vec.len();let mut sz = 1;while sz < n {sz <<= 1;}let mut dat = vec![M::id(); sz << 1];for i in 0..n {dat[i + sz] = vec[i].clone();}for k in (1..sz).rev() {dat[k] = dat[k << 1].op(&dat[(k << 1) + 1]);}return LazySegTree {dat: dat,lzy: vec![O::id(); sz << 1],need_update: vec![false; sz << 1],size: sz,};}pub fn eval(&mut self, l: usize, r: usize, k: usize) {if !self.need_update[k] {return;}self.dat[k] = self.lzy[k].act(&self.dat[k], r - l);if (k << 1) < self.dat.len() {self.lzy[k << 1] = self.lzy[k << 1].op(&self.lzy[k]);self.lzy[(k << 1) + 1] = self.lzy[(k << 1) + 1].op(&self.lzy[k]);self.need_update[k << 1] = true;self.need_update[(k << 1) + 1] = true;}self.lzy[k] = O::id();self.need_update[k] = false;}pub fn update(&mut self, a: usize, b: usize, x: O) {let sz = self.size;self._update(a, b, &x, 0, sz, 1);}pub fn _update(&mut self, a: usize, b: usize, x: &O, l: usize, r: usize, k: usize) {self.eval(l, r, k);if b <= l || r <= a {return;} else if a <= l && r <= b {self.lzy[k] = self.lzy[k].op(x);self.need_update[k] = true;self.eval(l, r, k);} else {let mid = (l + r) >> 1;self._update(a, b, x, l, mid, k << 1);self._update(a, b, x, mid, r, (k << 1) + 1);self.dat[k] = self.dat[k << 1].op(&self.dat[(k << 1) + 1]);}}pub fn query(&mut self, a: usize, b: usize) -> M {let sz = self.size;return self._query(a, b, 0, sz, 1);}pub fn _query(&mut self, a: usize, b: usize, l: usize, r: usize, k: usize) -> M {self.eval(l, r, k);if b <= l || r <= a {return M::id();} else if a <= l && r <= b {return self.dat[k].clone();} else {let mid = (l + r) >> 1;let vl = self._query(a, b, l, mid, k << 1);let vr = self._query(a, b, mid, r, (k << 1) + 1);return vl.op(&vr);}}}struct SegTree<M: Monoid> {dat: Vec<M>,size: usize,}impl<M: Monoid + Clone> SegTree<M> {pub fn new(n: usize) -> SegTree<M> {let mut sz = 1;while sz < n {sz <<= 1;}SegTree::<M> {dat: vec![M::id(); sz * 2],size: sz,}}pub fn update(&mut self, k: usize, val: M) {let mut k = k + self.size;self.dat[k] = val;while k > 0 {k = k >> 1;self.dat[k] = self.dat[k << 1].op(&self.dat[(k << 1) + 1]);}}pub fn query(&self, a: usize, b: usize) -> M {let mut lx = M::id();let mut rx = M::id();let mut l = a + self.size;let mut r = b + self.size;while l < r {if (l & 1) == 1 {lx = lx.op(&self.dat[l]);l += 1;}if (r & 1) == 1 {r -= 1;rx = self.dat[r].op(&rx);}l >>= 1;r >>= 1;}return lx.op(&rx);}}fn decode(v: Vec<char>) -> Vec<(char, usize)> {let mut res = Vec::new();let mut now = v[0];let mut cnt = 1;for i in 1..v.len() {if v[i] == now {cnt += 1;} else {res.push((now, cnt));cnt = 1;now = v[i];}}res.push((now, cnt));return res;}pub mod mod_int {use super::algebra::{One, Zero};use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};type Num = usize;const MOD: usize = 1e9 as usize + 7;#[derive(Clone, Copy)]pub struct ModInt<T: Copy + Clone>(pub T);impl Add<ModInt<Num>> for ModInt<Num> {type Output = ModInt<Num>;fn add(self, rhs: ModInt<Num>) -> ModInt<Num> {self + rhs.0}}impl Add<Num> for ModInt<Num> {type Output = ModInt<Num>;fn add(self, mut rhs: Num) -> ModInt<Num> {if rhs >= MOD {rhs %= MOD;}let mut t = rhs + self.0;if t >= MOD {t = t - MOD;}ModInt(t)}}impl Sub<Num> for ModInt<Num> {type Output = ModInt<Num>;fn sub(self, rhs: Num) -> ModInt<Num> {let rhs = if rhs >= MOD { rhs % MOD } else { rhs };let value = if self.0 < rhs { self.0 + MOD } else { self.0 };ModInt(value - rhs)}}impl Sub<ModInt<Num>> for ModInt<Num> {type Output = ModInt<Num>;fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> {self - rhs.0}}impl AddAssign<Num> for ModInt<Num> {fn add_assign(&mut self, other: Num) {*self = *self + other;}}impl AddAssign<ModInt<Num>> for ModInt<Num> {fn add_assign(&mut self, other: ModInt<Num>) {*self = *self + other;}}impl SubAssign<Num> for ModInt<Num> {fn sub_assign(&mut self, other: Num) {*self = *self - other;}}impl SubAssign<ModInt<Num>> for ModInt<Num> {fn sub_assign(&mut self, other: ModInt<Num>) {*self = *self - other;}}impl Div<Num> for ModInt<Num> {type Output = ModInt<Num>;fn div(self, mut rhs: Num) -> ModInt<Num> {if rhs >= MOD {rhs %= MOD;}self * ModInt(rhs).pow(MOD - 2)}}impl Div<ModInt<Num>> for ModInt<Num> {type Output = ModInt<Num>;fn div(self, rhs: ModInt<Num>) -> ModInt<Num> {self / rhs.0}}impl DivAssign<Num> for ModInt<Num> {fn div_assign(&mut self, rhs: Num) {*self = *self / rhs}}impl DivAssign<ModInt<Num>> for ModInt<Num> {fn div_assign(&mut self, rhs: ModInt<Num>) {*self = *self / rhs}}impl Mul<ModInt<Num>> for ModInt<Num> {type Output = ModInt<Num>;fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> {self * rhs.0}}impl Mul<Num> for ModInt<Num> {type Output = ModInt<Num>;fn mul(self, mut rhs: Num) -> ModInt<Num> {if rhs >= MOD {rhs %= MOD;}let t = (self.0 * rhs) % MOD;ModInt(t)}}impl MulAssign<Num> for ModInt<Num> {fn mul_assign(&mut self, rhs: Num) {*self = *self * rhs;}}impl MulAssign<ModInt<Num>> for ModInt<Num> {fn mul_assign(&mut self, rhs: ModInt<Num>) {*self = *self * rhs;}}impl ModInt<Num> {pub fn pow(self, e: Num) -> ModInt<Num> {let mut result = ModInt(1);let mut cur = self;let mut e = e;while e > 0 {if e & 1 == 1 {result *= cur;}e >>= 1;cur *= cur;}result}}impl Zero for ModInt<Num> {fn zero() -> Self {ModInt(0)}}impl One for ModInt<Num> {fn one() -> Self {ModInt(1)}}}struct Eratosthenes {n: usize,prime: Vec<bool>,}impl Eratosthenes {pub fn new(n: usize) -> Eratosthenes {let mut prime = vec![true; n + 1];prime[0] = false;prime[1] = false;let mut i = 2;while i * i <= n {if prime[i] {let mut p = i * 2;while p <= n {prime[p] = false;p += i;}}i += 1;}Eratosthenes { n: n, prime: prime }}}pub mod matrix {use super::algebra::{One, Zero};use std::ops::{Add, Mul};#[derive(Clone)]pub struct Matrix<T: Add + Mul + Clone + Copy + One + Zero>(pub Vec<Vec<T>>);impl<T: Add<Output = T> + Mul<Output = T> + Clone + Copy + One + Zero> Matrix<T> {pub fn mul(&mut self, rhs: &Matrix<T>) -> Matrix<T> {let n = self.0.len();let m = rhs.0[0].len();let p = self.0[0].len();let mut res = vec![vec![T::zero(); m]; n];for i in 0..n {for j in 0..m {for k in 0..p {res[i][j] = res[i][j] + self.0[i][k] * rhs.0[k][j]}}}return Matrix(res);}// pub fn update(&mut self) -> Vec<Vec<T>> {// let m = self.mat.len();// let mut res = vec![vec![T::zero(); m]; m];// for i in 0..m {// for j in 0..m {// for k in 0..m {// res[i][j] = res[i][j] + self.mat[i][k] * self.mat[k][j];// }// }// }// return res;// }pub fn pow(&mut self, k: usize) -> Matrix<T> {let n = self.0.len();let mut k = k;let mut res = Matrix(vec![vec![T::zero(); n]; n]);let mut b = (*self).clone();for i in 0..n {res.0[i][i] = T::one();}while k > 0 {if k & 1 == 1 {res = b.mul(&res);}b = b.mul(&b.clone());k >>= 1;}return res;}}}#[derive(Clone, Copy)]struct Alpha(i64);impl Monoid for Alpha {fn id() -> Self {Alpha(0i64)}fn op(&self, rhs: &Self) -> Self {Alpha(self.0 | rhs.0)}}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 ok = self.len() as i32;let mut ng = -1i32;while ok - ng > 1 {let mid = ((ok + ng) / 2);match self[mid as usize].cmp(&x) {Ordering::Greater | Ordering::Equal => {ok = mid;}Ordering::Less => {ng = mid;}}}return ok as usize;}fn upper_bound(&self, x: T) -> usize {let mut ok = self.len() as i32;let mut ng = -1i32;while ok - ng > 1 {let mid = ((ok + ng) / 2);match self[mid as usize].cmp(&x) {Ordering::Greater => {ok = mid;}Ordering::Equal | Ordering::Less => {ng = mid;}}}return ok as usize;}}fn solve() {input! {a: usize,b: usize}let tmp = min(a, b);if a == b {println!("{}", a * 2 - 1);} else {println!("{}", tmp * 2);}}fn main() {// input! {// t: usize// }let mut t = 1;for _ in 0..t {solve();}}