use std::io; 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() { 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 sol = vec![]; let mut rng = PcgXshRr::new(123, 456); for _ in 0..50 { let r1 = rng.gen_range(0, 45) as usize; let r2 = rng.gen_range(0, 45) as usize; let front = ((a[r1].0 + a[r2].0) as f64 / 2f64).ceil() as u64; let back = ((a[r1].1 + a[r2].1) as f64 / 2f64).ceil() as u64; a[r1] = (front, back); a[r2] = (front, back); sol.push((r1 + 1, r2 + 1)); } let mut best_score = calc_score(&sol); eprintln!("score = {}", best_score); let mut timer = Timer::new(0.98); while !timer.is_timeout() { let r1 = rng.gen_range(0, 50) as usize; let r2 = rng.gen_range(0, 50) as usize; let mut copy_sol = sol.clone(); copy_sol.swap(r1, r2); let new_score = calc_score(©_sol); if new_score > best_score { best_score = new_score; sol = copy_sol; eprintln!("score = {}", best_score); } } println!("{}", sol.len()); for (r1, r2) in sol { let r2 = if r1 == r2 { r2 + 1 } else { r2 }; println!("{} {}", r1, r2); } } fn calc_score(sol: &[(usize, usize)]) -> usize { let d1 = (sol[0].0 as i32 - ANS as i32).abs(); let d2 = (sol[0].1 as i32 - ANS as i32).abs(); (2000000f64 - 100000f64 * (d1.max(d2) as f64 + 1f64).log10()).ceil() as usize }