SHARE
TWEET

Untitled

a guest Jul 24th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #[allow(unused_imports)]
  2. use std::cmp::{max, min};
  3. use std::{
  4.     error::Error,
  5.     io::{stdin, stdout, BufWriter, Write},
  6. };
  7.  
  8. #[derive(Default)]
  9. struct Scanner {
  10.     buffer: Vec<String>,
  11. }
  12.  
  13. impl Scanner {
  14.     fn next<T: std::str::FromStr>(&mut self) -> T {
  15.         loop {
  16.             if let Some(token) = self.buffer.pop() {
  17.                 return token.parse().ok().expect("Failed parse");
  18.             }
  19.             let mut input = String::new();
  20.             stdin().read_line(&mut input).expect("Failed read");
  21.             self.buffer = input.split_whitespace().rev().map(String::from).collect();
  22.         }
  23.     }
  24. }
  25.  
  26. fn main() -> Result<(), Box<dyn Error>> {
  27.     let mut scan = Scanner::default();
  28.     let out = &mut BufWriter::new(stdout());
  29.     let n = scan.next::<usize>();
  30.     let m = scan.next::<usize>();
  31.     let mut topics = vec![];
  32.     (0..n).for_each(|_| topics.push(scan.next::<String>()));
  33.     let (total, all) = get_topics(topics, n, m)?;
  34.     writeln!(out, "{}", total)?;
  35.     writeln!(out, "{}", all)?;
  36.     Ok(())
  37. }
  38.  
  39. fn get_topics(topics: Vec<String>, n: usize, m: usize) -> Result<(usize, usize), Box<dyn Error>> {
  40.     let mut max_topics = 0;
  41.     let mut total_max = 0;
  42.  
  43.     for i in 0..(n - 1) {
  44.         for j in (i + 1)..n {
  45.             let one = usize::from_str_radix(&topics[i], 2)?;
  46.             let two = usize::from_str_radix(&topics[j], 2)?;
  47.             let set_bits = count_set_bits(one | two);
  48.             if set_bits > max_topics {
  49.                 max_topics = set_bits;
  50.                 total_max = 1;
  51.             } else if set_bits == max_topics {
  52.                 total_max += 1;
  53.             }
  54.         }
  55.     }
  56.     Ok((max_topics, total_max))
  57. }
  58.  
  59. fn count_set_bits(n: usize) -> usize {
  60.     let mut n = n;
  61.     let mut count = 0;
  62.     while n > 0 {
  63.         n &= n - 1;
  64.         count += 1;
  65.     }
  66.     count
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top