#476174 (Rust) No.453 製薬会社

• 問題: No.453 製薬会社
• ユーザー: niuez
• 提出日時: 2020-05-04 18:01:04
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 8,832 bytes
• コンパイル時間: 1,739 ms
• コンパイル使用メモリ: 165,784 KB
• 実行使用メモリ: 4,384 KB
• 最終ジャッジ日時: 2023-09-07 00:43:52
• 合計ジャッジ時間: 2,700 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	1 ms; 4,384 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	1 ms; 4,376 KB
testcase_06	AC	1 ms; 4,380 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	1 ms; 4,380 KB
testcase_09	AC	1 ms; 4,380 KB
testcase_10	AC	1 ms; 4,376 KB
testcase_11	AC	1 ms; 4,376 KB
testcase_12	AC	1 ms; 4,380 KB

コンパイルメッセージ

warning: variable `C` should have a snake case name
  --> Main.rs:13:13
   |
13 |     scan! { C: f64, D: f64, }
   |             ^ help: convert the identifier to snake case (notice the capitalization): `c`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `D` should have a snake case name
  --> Main.rs:13:21
   |
13 |     scan! { C: f64, D: f64, }
   |                     ^ help: convert the identifier to snake case: `d`

warning: 2 warnings emitted

ソースコード

fn main() {
    ioset! { inp, buf }
    macro_rules! scan {
        ($($r:tt)*) => {
            input! { inp, $($r)* }
        }
    }
    macro_rules! print {
        ($($t:expr),*) => {
            write!(buf, $($t),*).unwrap();
        } 
    }
    scan! { C: f64, D: f64, }
    let mut xrsh = Xorshift::new();
    let ans = seidel_lp(&mut xrsh, 2, &[1.0, 2.0], &[(vec![3.0 / 4.0, 2.0 / 7.0], C), (vec![1.0 / 4.0, 5.0 / 7.0], D), (vec![-1.0, 0.0], 0.0), (vec![0.0, -1.0], 0.0)], &[(0.0, 2000.0), (0.0, 2000.0)]).unwrap();
    print!("{:.10}\n", ans[0] * 1000.0 + ans[1] * 2000.0);
}

pub trait ToVec {
    type Item;
    fn tovec(self) -> Vec<Self::Item>;
}

impl<I: std::iter::Iterator> ToVec for I {
    type Item = <Self as std::iter::Iterator>::Item;
    fn tovec(self) -> Vec<Self::Item> {
        self.collect::<Vec<Self::Item>>()
    }
}

#[derive(Debug)]
#[allow(dead_code)]
pub struct Xorshift {
    seed: u64,
}
impl Xorshift {
    #[allow(dead_code)]
    pub fn new() -> Xorshift {
        Xorshift {
            seed: 0xf0fb588ca2196dac,
        }
    }
    #[allow(dead_code)]
    pub fn with_seed(seed: u64) -> Xorshift {
        Xorshift { seed }
    }
    #[inline]
    #[allow(dead_code)]
    pub fn next(&mut self) -> u64 {
        self.seed = self.seed ^ (self.seed << 13);
        self.seed = self.seed ^ (self.seed >> 7);
        self.seed = self.seed ^ (self.seed << 17);
        self.seed
    }
    #[inline]
    #[allow(dead_code)]
    pub fn rand(&mut self, m: u64) -> u64 {
        self.next() % m
    }
    #[inline]
    #[allow(dead_code)]
    // 0.0 ~ 1.0
    pub fn randf(&mut self) -> f64 {
        use std::mem;
        const UPPER_MASK: u64 = 0x3FF0000000000000;
        const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
        let tmp = UPPER_MASK | (self.next() & LOWER_MASK);
        let result: f64 = unsafe { mem::transmute(tmp) };
        result - 1.0
    }
}


pub fn seidel_lp(xrsh: &mut Xorshift, d: usize, c: &[f64], mat: &[(Vec<f64>, f64)], bounds: &[(f64, f64)]) -> Option<Vec<f64>> {
    match d {
        0 => unreachable!("0 dimension"),
        1 => {
            assert!(c.len() == 1, "length of c must be 1 at this point");
            let (low, high) = bounds[0];
            let (h, l, z) = mat
                .iter()
                .fold((high, low, 0f64), |(h, l, z), (a, p)| {
                    assert!(a.len() == 1, "length of a must be 1 at this point");
                    match a[0].partial_cmp(&0f64) {
                        None => unreachable!("a[0] is Nan?"),
                        Some(Ordering::Greater) => {
                            let nh = if p / a[0] <= h { p / a[0] } else { h };
                            (nh, l, z)
                        }
                        Some(Ordering::Less) => {
                            let nl = if p / a[0] >= l { p / a[0] } else { l };
                            (h, nl, z)
                        }
                        Some(Ordering::Equal) => {
                            let nz = if *p <= z { *p } else { z };
                            (h, l, nz)
                        }
                    }
                });
            if z < 0f64 || h < l {
                None
            }
            else if c[0] >= 0f64 { Some(vec![h]) }
            else { Some(vec![l]) }
        }
        d if mat.is_empty() => {
            Some((0..d).map(|i| if c[i] >= 0f64 { bounds[i].1 } else { bounds[i].0 }).collect())
        }
        d => {
            let rmi = (xrsh.next() as usize) % mat.len();
            let (a, ap) = mat[rmi].clone();
            let next_mat = (0..mat.len()).filter(|i| *i != rmi).map(|i| mat[i].clone()).collect::<Vec<_>>();
            let v = if let Some(v) = seidel_lp(xrsh, d, c, &next_mat, bounds) { v } else { return None };
            let value: f64 = (0..d)
                .map(|i| a[i] * v[i])
                .sum();
            if  value <= ap {
                    Some(v)
                }
            else {
                let k = if let Some(k) = (0..d).rev().find(|i| a[*i] != 0f64) { k } else { return None };
                let next_bounds = (0..d).filter(|i| *i != k).map(|i| bounds[i].clone()).collect::<Vec<_>>();
                let mut bar_mat = next_mat.iter().map(|(b, bp)| {
                    let ratio = b[k] / a[k];
                    let v = (0..d)
                        .filter(|i| *i != k)
                        .map(|i| {
                            b[i] - ratio * a[i]
                        })
                        .collect::<Vec<_>>();
                    (v, bp - ratio * ap)
                }).collect::<Vec<_>>();
                let bar_c = (0..d)
                    .filter(|i| *i != k)
                    .map(|i| {
                        c[i] - (c[k] / a[k]) * a[i]
                    }).collect::<Vec<_>>();

                let f = (0..d).filter(|i| *i != k).map(|i| {
                    - (1f64 / a[k]) * a[i]
                }).collect::<Vec<_>>();
                let fp = bounds[k].1;
                let g = (0..d).filter(|i| *i != k).map(|i| {
                    - (1f64 / a[k]) * a[i]
                }).collect::<Vec<_>>();
                let gp = bounds[k].0;
                bar_mat.push((f, fp));
                bar_mat.push((g, gp));

                if let Some(mut v) = seidel_lp(xrsh, d - 1, &bar_c, &bar_mat, &next_bounds) {
                    v.insert(k, 0f64);
                    let s: f64 = (0..d)
                        .map(|i| a[i] * v[i])
                        .sum();
                    v[k] = (ap - s) / a[k];
                    Some(v)
                } else {
                    None
                }

            }
        }
    }
}

/* I/O */

use std::io::{ stdout, BufWriter, Write };

#[macro_export]
macro_rules! ioset {
    ($inp:ident, $buf:ident) => {
        inset!($inp);
        outset!($buf);
    }
}

#[macro_export]
macro_rules! inset {
    (source = $s:expr, $iter:ident) => {
        let mut $iter = $s.split_whitespace();
    };
    ($iter:ident) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut $iter = s.split_whitespace();
    }
}

#[macro_export]
macro_rules! input {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt, $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input! { $iter, $($r)* }
    };
    ($iter:expr, mut $var:ident : $t:tt, $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input! { $iter, $($r)* }
    };
    ($iter:expr, ($var:expr) : $t:tt, $($r:tt)*) => {
        $var = read_value!($iter, $t);
        input! { $iter, $($r)* }
    };
}

#[macro_export]
macro_rules! read_value {

    // tuple
    ($iter:expr, ( $($t:tt), * )) => {
        ( $(read_value!($iter, $t)), * )
    };
    
    // array
    ($iter:expr, [ $t:tt; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    
    // string
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    
    // any other
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[macro_export]
macro_rules! outset {
    ($buf:ident) => {
        let sout = stdout();
        let mut $buf = BufWriter::new(sout.lock());
    }
}

#[macro_export]
macro_rules! output {
    ($buf:expr, $($t:expr),*) => {
        write!($buf, $($t),*).unwrap();
    }
}

struct Chars<'a>(&'a Vec<char>);

impl<'a> std::fmt::Display for Chars<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        write!(f, "{}", self.0.iter().collect::<String>())
    }
}

use std::cmp::Ordering;

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 ng = -1i64;
        let mut ok = self.len() as i64;
        while ok - ng > 1 {
            let m = (ok + ng) / 2;
            match self[m as usize].cmp(x) {
                Ordering::Greater | Ordering::Equal => {
                    ok = m;
                }
                _ => {
                    ng = m;
                }
            }
        }
        ok as usize
    }
    fn upper_bound(&self, x: &T) -> usize {
        let mut ng = -1i64;
        let mut ok = self.len() as i64;
        while ok - ng > 1 {
            let m = (ok + ng) / 2;
            match self[m as usize].cmp(x) {
                Ordering::Greater => {
                    ok = m;
                }
                _ => {
                    ng = m;
                }
            }
        }
        ok as usize
    }
}