結果
| 問題 |
No.453 製薬会社
|
| ユーザー |
 niuez
|
| 提出日時 | 2020-05-04 18:03:03 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| コード長 | 7,780 bytes |
| コンパイル時間 | 16,804 ms |
| コンパイル使用メモリ | 378,824 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-24 19:23:48 |
| 合計ジャッジ時間 | 17,051 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 9 |
ソースコード
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);
}
use std::cmp::Ordering;
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>())
}
}
#[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
}
}