結果
問題 | No.546 オンリー・ワン |
ユーザー | sntea |
提出日時 | 2017-09-10 20:37:52 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,618 bytes |
コンパイル時間 | 14,890 ms |
コンパイル使用メモリ | 379,944 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 12:50:45 |
合計ジャッジ時間 | 15,229 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 4 ms
5,248 KB |
testcase_10 | AC | 4 ms
5,248 KB |
コンパイルメッセージ
warning: unused macro definition: `parse` --> src/main.rs:19:14 | 19 | macro_rules! parse { | ^^^^^ | = note: `#[warn(unused_macros)]` on by default warning: unused macro definition: `rvec` --> src/main.rs:44:14 | 44 | macro_rules! rvec { | ^^^^ warning: unused macro definition: `debug` --> src/main.rs:60:14 | 60 | macro_rules! debug { | ^^^^^ warning: variable `cnt` is assigned to, but never used --> src/main.rs:94:17 | 94 | let mut cnt = 0; | ^^^ | = note: consider using `_cnt` instead = note: `#[warn(unused_variables)]` on by default warning: function `printvec` is never used --> src/main.rs:66:4 | 66 | fn printvec<T>(v: &Vec<T>) where T: std::fmt::Display { | ^^^^^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
// use std::ops::{Index, IndexMut}; // use std::cmp::{Ordering, min, max}; // use std::collections::{BinaryHeap, BTreeMap}; // use std::collections::btree_map::Entry::{Occupied, Vacant}; // use std::clone::Clone; fn getline() -> String{ let mut res = String::new(); std::io::stdin().read_line(&mut res).ok(); res } macro_rules! split { ($x: expr) => { ($x).trim().split(' ').collect() } } macro_rules! parse { ($x: expr) => { ($x).parse().unwrap() } } macro_rules! readl { ($t: ty) => { { let s = getline(); let iv: Vec<_> = split!(s); let mut iter = iv.into_iter(); iter.next().unwrap().parse::<$t>().unwrap() } }; ($( $t: ty),+ ) => { { let s = getline(); let iv: Vec<_> = split!(s); let mut iter = iv.into_iter(); ($(iter.next().unwrap().parse::<$t>().unwrap(),)*) } }; } macro_rules! rvec { ($x: expr) => { ($x).into_iter().map(|x| parse!(x)).collect() } } macro_rules! readlvec { ($t: ty) => { { let s = getline(); let iv: Vec<_> = split!(s); iv.into_iter().map(|x| x.parse().unwrap()).collect::<Vec<$t>>() } } } macro_rules! debug { ($x: expr) => { println!("{}: {}", stringify!($x), $x) } } fn printvec<T>(v: &Vec<T>) where T: std::fmt::Display { for (i,e) in v.into_iter().enumerate() { if i != 0 { print!(" "); } print!("{}", e); } println!(""); } fn gcd(x: u64, y: u64) -> u64{ if x == 0 { y } else { gcd(y%x, x) } } fn main() { let (n,l,h) = readl!(usize, u64, u64); let c = readlvec!(u64); const INF: u64 = 1e15 as u64; let mut memo0 = vec![INF; 1<<n]; let mut memo1 = vec![INF; 1<<n]; fn rec(memo: &mut Vec<u64>, mask: usize, n: usize, c: &Vec<u64>, x: u64) -> u64 { if memo[mask] != INF { return memo[mask]; } let mut cnt = 0; let mut mul = 1; for i in 0..n { if (mask>>i)&1 == 1 { mul = mul*c[i]/gcd(mul, c[i]); } else { cnt += 1; } } memo[mask] = x/mul; for a in mask+1..1<<n { if a == mask|a { memo[mask] -= rec(memo, a, n, c, x); } } memo[mask] } let mut ans = 0; for i in 0..n { ans += rec(&mut memo0, 1<<i, n, &c, h) - rec(&mut memo1, 1<<i, n, &c, l-1); } println!("{}", ans); }