use std::io; use std::env; use std::time::Instant; const ANS: usize = 500_000_000_000_000_000; struct Timer { start: Instant, end: f64, } impl Timer { fn new(end: f64) -> Timer { Timer { start: Instant::now(), end, } } fn reset(&mut self) { self.start = Instant::now(); } fn elapsed(&self) -> f64 { #[cfg(feature = "local")] { self.start.elapsed().as_secs_f64() * 2.0 } #[cfg(not(feature = "local"))] { self.start.elapsed().as_secs_f64() } } fn is_timeout(&self) -> bool { self.elapsed() >= self.end } } pub struct PcgXshRr { state: u64, inc: u64, } impl PcgXshRr { // 新しい PcgXshRr インスタンスを作成するメソッド pub fn new(seed: u64, inc: u64) -> Self { let mut pcg = PcgXshRr { state: 0, inc }; pcg.seed(seed); pcg } // シードを設定するメソッド pub fn seed(&mut self, seed: u64) { self.state = 0; self.inc = (seed << 1) | 1; self.next(); // 初期値を生成する self.state = self.state.wrapping_add(seed); } // 次の乱数を生成するメソッド pub fn next(&mut self) -> u64 { let old_state = self.state; self.state = old_state .wrapping_mul(6364136223846793005) .wrapping_add(self.inc); let xorshifted = ((old_state >> 18) ^ old_state) >> 27; let rot = old_state >> 59; (xorshifted >> rot) | (xorshifted << ((-(rot as i32)) & 31)) } // 指定した範囲の乱数を生成するメソッド pub fn gen_range(&mut self, start: u64, end: u64) -> u64 { if start >= end { panic!("Invalid range"); } start + self.next() % (end - start) } } fn main() { env::set_var("RUST_BACKTRACE", "1"); let mut n = String::new(); io::stdin().read_line(&mut n).expect("Failed to read line"); let n: usize = n.trim().parse().expect("Failed to parse N"); let mut a: Vec<(u64, u64)> = Vec::new(); for _ in 0..n { let mut input = String::new(); io::stdin() .read_line(&mut input) .expect("Failed to read line"); let pair: Vec = input .split_whitespace() .map(|s| s.parse().expect("Failed to parse u64")) .collect(); if pair.len() == 2 { a.push((pair[0], pair[1])); } else { panic!("Invalid input format for A_i B_i"); } } let mut best_score = 0; let mut sol = vec![]; // let mut rng = PcgXshRr::new(123, 456); let timer = Timer::new(0.98); while ! timer.is_timeout() { let f_now = a[0].0; let b_now = a[0].1; let mut current_best = best_score; let mut next_action = (1, 2); for i in 1..n { let f_new = ((f_now + a[i].0) as f64 / 2f64).ceil() as u64; let b_new = ((b_now + a[i].1) as f64 / 2f64).ceil() as u64; let new_score = calc_score((f_new, b_new)); if new_score > current_best { current_best = new_score; next_action = (1, i + 1); } } if current_best > best_score { best_score = current_best; a[0].0 = ((f_now + a[next_action.0 - 1].0) as f64 / 2f64).ceil() as u64; a[0].1 = ((b_now + a[next_action.1 - 1].1) as f64 / 2f64).ceil() as u64; sol.push(next_action); } } eprintln!("inisol score = {}", best_score); println!("{}", sol.len()); for (r1, r2) in sol { let r2 = if r1 == r2 { r2 + 1 } else { r2 }; println!("{} {}", r1, r2); } eprintln!("best score = {}", best_score); std::process::exit(0); } fn calc_score(sol: (u64, u64)) -> usize { let d1 = (sol.0 as i64 - ANS as i64).abs(); let d2 = (sol.1 as i64 - ANS as i64).abs(); (2000000f64 - 100000f64 * (d1.max(d2) as f64 + 1f64).log10()).ceil() as usize }