結果
問題 | No.1701 half price |
ユーザー |
![]() |
提出日時 | 2021-10-08 22:51:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 142 ms / 3,000 ms |
コード長 | 9,077 bytes |
コンパイル時間 | 12,398 ms |
コンパイル使用メモリ | 402,196 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 06:01:32 |
合計ジャッジ時間 | 14,358 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
コンパイルメッセージ
warning: unused import: `std::cmp` --> src/main.rs:2:5 | 2 | use std::cmp; | ^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `std::cmp::min` --> src/main.rs:3:5 | 3 | use std::cmp::min; | ^^^^^^^^^^^^^ warning: unused import: `std::collections::BTreeMap` --> src/main.rs:4:5 | 4 | use std::collections::BTreeMap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::process` --> src/main.rs:5:5 | 5 | use std::process; | ^^^^^^^^^^^^ warning: unused import: `std::collections::HashSet` --> src/main.rs:8:5 | 8 | use std::collections::HashSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::BTreeSet` --> src/main.rs:10:5 | 10 | use std::collections::BTreeSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::BinaryHeap` --> src/main.rs:12:5 | 12 | use std::collections::BinaryHeap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused imports: `Hash`, `Hasher` --> src/main.rs:13:17 | 13 | use std::hash::{Hash, Hasher}; | ^^^^ ^^^^^^ warning: unnecessary parentheses around `while` condition --> src/main.rs:143:10 | 143 | while(b>0){ | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 143 - while(b>0){ 143 + while b>0 { | warning: unnecessary parentheses around `while` condition --> src/main.rs:159:14 | 159 | while(n != 0){ | ^ ^ | help: remove these parentheses | 159 - while(n != 0){ 159 + while n != 0 { | warning: unnecessary parentheses around `if` condition --> src/main.rs:160:16 | 160 | if (n&1 == 1){ans = ans*x%MODu;} | ^ ^ | help: remove these parentheses | 160 - if (n&1 == 1){ans = ans*x%MODu;} 160 + if n&1 == 1 {ans = ans*x%MODu;} | warning: unnecessary p
ソースコード
use std::cmp::Ordering;use std::cmp;use std::cmp::min;use std::collections::BTreeMap;use std::process;use std::cmp::Ord;use std::collections::HashMap;use std::collections::HashSet;use std::collections::VecDeque;use std::collections::BTreeSet;use std::mem;use std::collections::BinaryHeap;use std::hash::{Hash, Hasher};pub struct Scanner<R> {stdin: R,}impl<R: std::io::Read> Scanner<R> {pub fn read<T: std::str::FromStr>(&mut self) -> T {use std::io::Read;let buf = self.stdin.by_ref().bytes().map(|b| b.unwrap()).skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r').take_while(|&b| b != b' ' && b != b'\n' && b != b'\r').collect::<Vec<_>>();std::str::from_utf8(&buf).unwrap().parse().ok().expect("Parse error.")}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()}}pub trait BinarySearch<T> {fn lower_bound(&self, x:&T) -> usize;fn upper_bound(&self, x:&T) -> usize;}impl<T: Ord> BinarySearch<T> for VecDeque<T>{fn lower_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less => {low = mid + 1;}Ordering::Equal | Ordering::Greater => {high = mid;}}}low}fn upper_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less | Ordering::Equal => {low = mid + 1;}Ordering::Greater => {high = mid;}}}low}}impl<T: Ord> BinarySearch<T> for [T]{fn lower_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less => {low = mid + 1;}Ordering::Equal | Ordering::Greater => {high = mid;}}}low}fn upper_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less | Ordering::Equal => {low = mid + 1;}Ordering::Greater => {high = mid;}}}low}}fn comb(a:usize, b:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{let mut a = a;let mut b = b;if a == 0 && b == 0{return 1;}if a<b || a<0{return 0;}let mut tmp = ifac[a-b]*ifac[b]%MODu;return tmp * fac[a]%MODu;}fn nHr(n:usize, r:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{if n == 0 && r == 0{return 1;}return comb(n+r-1, r, fac, ifac);}fn modinv(a:usize, M:usize)->usize{let mut b = M as i64;let mut u = 1 as i64;let mut v = 0 as i64;let mut a = a as i64;let mut m = M as i64;while(b>0){let mut t = a/b;a -= t*b;mem::swap(&mut a, &mut b);u-=t*v;mem::swap(&mut u, &mut v);}u%=m;if u<0{u+=m;}return u as usize;}fn modpow(x:usize, n:usize) -> usize{let mut ans = 1;let mut n = n as usize;let mut x = x;while(n != 0){if (n&1 == 1){ans = ans*x%MODu;}x = x*x%MODu;n = n>>1;}ans}fn modpow2(x:i64, n:i64, m:i32) -> i64{let mut ans = 1;let mut n = n as i64;let mut x = x;while(n != 0){if (n&1 == 1){ans = ans*x%m as i64;}x = x*x%m as i64;n = n>>1;}ans}fn invs(max:usize)->(Vec<usize>, Vec<usize>){let mut fac = vec![0;max+1];let mut ifac = vec![0;max+1];fac[0] = 1;ifac[0] = 1;for i in 0..max{fac[i+1] = fac[i] * (i+1)%MODu;ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu;}(fac, ifac)}#[derive(Copy, Clone, Eq, PartialEq)]struct x{a:i64,b:i64,c:i64,d:i64,}impl Ord for x{fn cmp(&self, other:&Self)->Ordering{(other.b * (self.a)).cmp(&((self.b)*other.a))}}impl PartialOrd for x {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {Some(self.cmp(other))}}fn gcd(a:usize, b:usize)->usize{if b==0{return a;}return gcd(b, a%b);}fn prime_factor(n:usize)->HashMap<usize, usize>{let mut res = HashMap::new();let mut n = n;for i in 2..n{if i*i>n{break;}while(n%i==0){*res.entry(i).or_insert(0)+=1;n/=i;}}if n != 1{res.insert(n, 1);}res}fn usize_multiply_is_overflow(a:usize, b:usize)->bool{if a<std::usize::MAX/b{return false;}else{return true;}}fn pow2(x:usize, n:usize) -> usize{let mut ans = 1;let mut n = n;let mut x = x;while(n != 0){if (n&1 == 1){if usize_multiply_is_overflow(ans, x){return 0;}ans = ans*x;}n = n>>1;if n == 0{break;}if usize_multiply_is_overflow(x, x){return 0;}x = x*x;}ans}fn tmp(x:usize, y:usize)->usize{let mut ub = x+1;let mut lb = 1;while(ub-lb>1){let mut mid = (ub+lb)/2;let mut now = pow2(mid, y);let mut ok = true;if now == 0{ok = false;}if now>x {ok = false;}if ok{lb = mid;}else{ub = mid;}}return lb;}struct segment_tree<I, Op>{n: usize,dat: Vec<I>,op:Op,e:I,}impl<I, Op> segment_tree<I, Op>where Op: Fn(I, I) -> I, I:Copy{pub fn new(n_:usize, op: Op, e:I)->Self{let mut n = 1;while(n<n_){n*=2;}segment_tree{n: n, dat:vec![e; 2*n-1], op:op, e:e}}pub fn update(&mut self, k:usize, a:I){let mut k = k;k += self.n-1;self.dat[k] = a;while(k>0){k = (k-1)/2;self.dat[k] = (self.op)(self.dat[k*2 + 1], self.dat[k*2+2]);}}pub fn query_sub(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> I{if r<=a || b<=l{return self.e;}if a<=l && r<=b{return self.dat[k];}else{let mut vl = self.query_sub(a, b, k*2+1, l, (l+r)/2);let mut vr = self.query_sub(a, b, k*2+2, (l+r)/2, r);return (self.op)(vl, vr);}}pub fn query(&self, a:usize, b:usize)->I{return self.query_sub(a, b, 0, 0, self.n);}}fn solve(){let sssss = std::io::stdin();let mut sc = Scanner { stdin: sssss.lock() };let mut N:usize = sc.read();let mut W:i64 = sc.read();let mut a = vec![0i64;N];for i in 0..N{a[i] = sc.read();}let mut res = 0i64;for i in 1..1<<N{let mut ok = false;let mut t = i;while(true){let mut tmp = 0;for j in 0..N{if (i>>j)&1 == 1 {if (t>>j)&1 == 1{tmp+=a[j]/2;}else{tmp+=a[j];}}}if tmp == W{ok = true;}if t == 0{break;}t = (t-1)&i;}if ok {res+=1;}}println!("{}", res);}fn main(){solve();}const PI:f64 = std::f64::consts::PI;pub static MOD:i64 = 998244353;pub static MODu:usize = 1000000007;pub static MODi32:i32 = 1000000007;pub static eps:f64 = 1e-6;const INF: i64 = 1 << 60;const INFu:usize = 1<<62;const INFu128:u128 = 1<<126;