pub mod input { use std::io::{BufRead, ErrorKind}; pub trait BytesRead { fn read_bytes(&mut self) -> Vec; } impl BytesRead for R { #[inline] fn read_bytes(&mut self) -> Vec { let mut res = Vec::new(); loop { let buf = match self.fill_buf() { Ok(buf) => buf, Err(e) if e.kind() == ErrorKind::Interrupted => continue, Err(e) => panic!("{}", e), }; let (done, used, buf) = match buf.iter().position(u8::is_ascii_whitespace) { Some(i) => (i > 0 || res.len() > 0, i + 1, &buf[..i]), None => (buf.is_empty(), buf.len(), buf), }; res.extend_from_slice(buf); self.consume(used); if done { return res; } } } } #[macro_export] macro_rules! read { ($r:expr, [$t:tt; $n:expr]) => ((0..$n).map(|_| read!($r, $t)).collect::>()); ($r:expr, [$t:tt]) => (read!($r, [$t; read!($r, usize)])); ($r:expr, ($($t:tt),*)) => (($(read!($r, $t)),*)); ($r:expr, Bytes) => ($r.read_bytes()); ($r:expr, String) => (String::from_utf8(read!($r, Bytes)).unwrap()); ($r:expr, Usize1) => (read!($r, usize) - 1); ($r:expr, $t:ty) => (read!($r, String).parse::<$t>().unwrap()); } #[macro_export] macro_rules! input { ($r:expr, $($($v:ident)* : $t:tt),* $(,)?) => { $(let $($v)* = read!($r, $t);)* }; } } use std::cmp::Ordering; use std::collections::BinaryHeap; use input::BytesRead; #[derive(Eq, PartialEq)] struct Candidate { a: u64, b: u64, i: usize, j: usize, } impl Candidate { fn new(a: u64, b: u64, i: usize, j: usize) -> Self { Self { a, b, i, j, } } } impl Ord for Candidate { fn cmp(&self, other: &Self) -> Ordering { (self.a * other.b).cmp(&(other.a * self.b)) .then_with(|| other.i.cmp(&self.i)) } } impl PartialOrd for Candidate { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } fn run(reader: &mut R, _writer: &mut W) { input! { reader, n: usize, m: usize, a: [u64; n], b: [u64; m], } let mut heap = BinaryHeap::new(); for i in 0..n { heap.push(Candidate::new(a[i], b[0], i, 0)); } for _ in 0..m { let candidate = heap.pop().unwrap(); let i = candidate.i; println!("{}", i + 1); let j = candidate.j + 1; if j < m { heap.push(Candidate::new(a[i], b[j], i, j)); } } } fn main() { let (stdin, stdout) = (std::io::stdin(), std::io::stdout()); let mut reader = std::io::BufReader::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); run(&mut reader, &mut writer); }