use std::io; use std::time::{Instant, Duration}; //use rand::{thread_rng, Rng}; //use rand::seq::SliceRandom; use std::f64; use crate::rand::Xoshiro256; const START_TEMP_EXACT: f64 = 1e4; const END_TEMP_EXACT: f64 = 1e1; const CHECK_NUM: usize = 10; const TIME_LIMIT: f64 = 0.85; fn move_element(vec: &Vec, i: usize, j: usize) -> Vec { let mut result = vec.clone(); // 元のベクタを複製して新しいベクタを作成 let element = result.remove(i); // `i`番目の要素を取り出す let insert_position = if j > i { j - 1 } else { j }; // 挿入位置を調整 result.insert(insert_position, element); // 要素を挿入 result } fn main() { let start_time = Instant::now(); let seed = 42; //let mut rng = thread_rng(); let mut rng = Xoshiro256::new(seed); let m = 50; let l: i64 = 5*10_i64.pow(17); let mut input_string = String::new(); io::stdin().read_line(&mut input_string).expect("Failed to read line"); let n: usize = input_string.trim().parse().expect("Please type a number!"); let mut a = vec![0; n]; let mut b = vec![0; n]; for i in 0..n { let mut input = String::new(); io::stdin().read_line(&mut input).expect("Failed to read line"); let parts: Vec = input .split_whitespace() .map(|x| x.parse().expect("Not an integer!")) .collect(); a[i] = parts[0]; b[i] = parts[1]; } let mut ans = Vec::new(); for _ in 0..(m-1) { let u = rng.gen_usize(0, n); let mut v = rng.gen_usize(0, n); while v == u { v = rng.gen_usize(0, n); } //let picks = (0..n).collect::>(); //let &u = picks.choose(&mut rng).unwrap(); //let &v = picks.choose(&mut rng).unwrap(); ans.push((u, v)); } //let v = rng.gen_range(1..n); let v = rng.gen_usize(1, n); ans.push((0, v)); let mut cost = calc_score(&a, &b, &ans, l); let mut iter = 0; let mut temperature = START_TEMP_EXACT; let mut best_ans = ans.clone(); let mut best_cost = cost; loop { iter += 1; iter += 1; if iter % CHECK_NUM == 0 { let ratio = get_time() / TIME_LIMIT; if ratio >= 1.0 { break; } temperature = START_TEMP_EXACT.powf(1.0 - ratio) * END_TEMP_EXACT.powf(ratio); } //let neigh = rng.gen_range(0..2); let neigh = rng.gen_usize(0, 2); if neigh == 0 { //let i = rng.gen_range(0..m); let i = rng.gen_usize(0, m); let pre = ans[i]; if i != m-1 { let u = rng.gen_usize(0, n); let mut v = rng.gen_usize(0, n); while v == u { v = rng.gen_usize(0, n); } //let picks = (0..n).collect::>(); //let &u = picks.choose(&mut rng).unwrap(); //let &v = picks.choose(&mut rng).unwrap(); ans[i] = (u, v); } else { //let v = rng.gen_range(1..n); let v = rng.gen_usize(1, n); ans[i] = (0, v); } let new_cost = calc_score(&a, &b, &ans, l); //if new_cost > cost { //ans[i] = pre; //} else { //cost = new_cost; //} if new_cost <= best_cost { best_ans = ans.clone(); best_cost = new_cost; } if new_cost <= cost { cost = new_cost; } else if rng.gen_bool(f64::exp((cost as f64 - new_cost as f64) / temperature)) { cost = new_cost; } else { ans[i] = pre; } } else { let i = rng.gen_usize(0, m); let j = rng.gen_usize(0, m); //let i = rng.gen_range(0..m-1); //let j = rng.gen_range(0..m-1); //ans.swap(i, j); let new_ans = move_element(&ans, i, j); let new_cost = calc_score(&a, &b, &new_ans, l); //if new_cost > cost { //ans.swap(i, j); // Swap back if not better //} else { //cost = new_cost; //} if new_cost <= best_cost { best_ans = new_ans.clone(); best_cost = new_cost; } if new_cost <= cost { cost = new_cost; ans = new_ans; } else if rng.gen_bool(f64::exp((cost as f64 - new_cost as f64) / temperature)) { cost = new_cost; ans = new_ans; } else { //ans.swap(i, j); continue; } } } println!("{}", best_ans.len()); for &(u, v) in &best_ans { println!("{} {}", u + 1, v + 1); } // Score printing to stderr in Rust is not straightforward as in Python // and typically not done in basic Rust programs. let score = if cost != 0 { (2000000.0 - 100000.0 * ((best_cost + 1) as f64).log10()) as i64 } else { 2000050 - ans.len() as i64 }; eprintln!("{}", score); } fn calc_score(a: &Vec, b: &Vec, ans: &Vec<(usize, usize)>, l: i64) -> i64 { let mut ac = a.clone(); let mut bc = b.clone(); for &(u, v) in ans { let x = (ac[u] + ac[v]) / 2; ac[u] = x; ac[v] = x; let y = (bc[u] + bc[v]) / 2; bc[u] = y; bc[v] = y; } let v1 = (l - ac[0]).abs(); let v2 = (l - bc[0]).abs(); std::cmp::max(v1, v2) } mod rand { pub(crate) struct Xoshiro256 { s0: u64, s1: u64, s2: u64, s3: u64, } impl Xoshiro256 { pub(crate) fn new(mut seed: u64) -> Self { let s0 = split_mix_64(&mut seed); let s1 = split_mix_64(&mut seed); let s2 = split_mix_64(&mut seed); let s3 = split_mix_64(&mut seed); Self { s0, s1, s2, s3 } } fn next(&mut self) -> u64 { let result = (self.s1 * 5).rotate_left(7) * 9; let t = self.s1 << 17; self.s2 ^= self.s0; self.s3 ^= self.s1; self.s1 ^= self.s2; self.s0 ^= self.s3; self.s2 ^= t; self.s3 = self.s3.rotate_left(45); result } pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize { assert!(lower < upper); let count = upper - lower; (self.next() % count as u64) as usize + lower } pub(crate) fn gen_i32(&mut self, lower: i32, upper: i32) -> i32 { assert!(lower < upper); let count = upper - lower; (self.next() % count as u64) as i32 + lower } pub(crate) fn gen_f64(&mut self) -> f64 { const UPPER_MASK: u64 = 0x3ff0000000000000; const LOWER_MASK: u64 = 0xfffffffffffff; let result = UPPER_MASK | (self.next() & LOWER_MASK); let result: f64 = unsafe { std::mem::transmute(result) }; result - 1.0 } pub(crate) fn gen_bool(&mut self, prob: f64) -> bool { self.gen_f64() < prob } } fn split_mix_64(x: &mut u64) -> u64 { *x += 0x9e3779b97f4a7c15; let mut z = *x; z = (z ^ z >> 30) * 0xbf58476d1ce4e5b9; z = (z ^ z >> 27) * 0x94d049bb133111eb; return z ^ z >> 31; } } pub fn get_time() -> f64 { static mut STIME: f64 = -1.0; // 初期値 let t = std::time::SystemTime::now() // nowを取得 .duration_since(std::time::UNIX_EPOCH) .unwrap(); // a.duration_since(b)だとa>bが前提 let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9; // as_secsが秒, .subsec_nanos()が小数点以下の秒 unsafe { if STIME < 0.0 { STIME = ms; // 経過時間の初期化 } // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利 #[cfg(feature = "local")] { // eprintln!("local"); (ms - STIME) * 0.9 } #[cfg(not(feature = "local"))] { ms - STIME } } }