use std::cmp::{max, min}; use std::io; use std::collections::BinaryHeap; use std::time::Instant; #[derive(Debug, Clone)] struct Node { cards: Vec<(i64, i64)>, score: i64, score2: i64, history: Vec<(usize, usize)>, } impl Eq for Node {} impl PartialEq for Node { fn eq(&self, other: &Self) -> bool { self.score == other.score } } impl Ord for Node { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.score.cmp(&other.score) } } impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } impl Node { fn new(cards: Vec<(i64, i64)>, history: Vec<(usize, usize)>, calced_score: i64) -> Self { let mut score = calced_score; if score <= -1 { score = Self::calc_score(&cards); } let score2 = Self::calc_score_2(&cards); Self { cards, score, score2, history, } } fn calc_score(cards: &Vec<(i64, i64)>) -> i64 { let mut max_score = 2000000; let target = 10_i64.pow(17) * 5; let mut result_score = 0; for i in 1..cards.len() { let new_card = ((cards[i].0 + cards[0].0) / 2, (cards[i].1 + cards[0].1) / 2); result_score = max(result_score, max_score - (100000.0 * (max((new_card.0 - target).abs(), (new_card.1 - target).abs()) as f64 + 1.0).log10()) as i64); } result_score } fn calc_score_2(cards: &Vec<(i64, i64)>) -> i64 { let mut max_score = 2000000; let target = 10_i64.pow(17) * 5; max_score - (100000.0 * (max((cards[0].0 - target).abs(), (cards[0].1 - target).abs()) as f64 + 1.0).log10()) as i64 } fn build_next(&self, turn: (usize, usize)) -> Self { let mut cards = self.cards.clone(); let new_card = ((cards[turn.0].0 + cards[turn.1].0) / 2, (cards[turn.0].1 + cards[turn.1].1) / 2); cards[turn.0] = new_card; cards[turn.1] = new_card; let mut history = self.history.clone(); history.push(turn); if turn.0 == 0 { Self::new(cards, history, -1) } else { let new_card_0 = ((cards[0].0 + new_card.0) / 2, (cards[0].1 + new_card.1) / 2); let mut score = self.score; let target = 10_i64.pow(17) * 5; score = max(score, 2000000 - (100000.0 * (max((new_card_0.0 - target).abs(), (new_card_0.1 - target).abs()) as f64 + 1.0).log10()) as i64); Self::new(cards, history, score) } } } struct Solver { n: usize, states: Vec>, searched_states: Vec>, time: Instant, } impl Solver { fn new(n: usize, cards: Vec<(i64, i64)>) -> Self { let mut states = vec![BinaryHeap::new(); 51]; let node = Node::new(cards, vec![], -1); states[0].push(node); let mut searched_states = vec![BinaryHeap::new(); 51]; let time = Instant::now(); Self { n, states, searched_states, time } } fn solve(&mut self) { let n = self.n; let target = 10_i64.pow(17) * 5; let time = Instant::now(); let mut itr = 0; while self.time.elapsed().as_millis() < 900 { itr += 1; for i in 0..50 { if self.time.elapsed().as_millis() >= 900 { return; } let state = &self.states[i].pop(); if state.is_none() { continue; } let state = state.as_ref().unwrap(); let cards = &state.cards; // eprintln!("{}: {}", itr, i + 1); // let mut best_score = BinaryHeap::new(); let mut new_states = BinaryHeap::new(); for p in 0..n { for q in p + 1..n { let next_state = state.build_next((p, q)); new_states.push(next_state); if self.time.elapsed().as_millis() >= 900 { return; } } } for _ in 0..min(100, new_states.len()) { let state = new_states.pop().unwrap(); self.states[i + 1].push(state.clone()); if self.time.elapsed().as_millis() >= 900 { return; } } self.searched_states[i].push(state.clone()); } } } fn print(&self) { let mut ans_state = None; for i in 0..51 { if !self.states[i].is_empty() { if ans_state.is_none() { ans_state = Some(self.states[i].peek().unwrap().clone()); } if self.states[i].peek().unwrap().score2 > ans_state.as_ref().unwrap().score2 { ans_state = Some(self.states[i].peek().unwrap().clone()); } } if !self.searched_states[i].is_empty() { if ans_state.is_none() { ans_state = Some(self.searched_states[i].peek().unwrap().clone()); } if self.searched_states[i].peek().unwrap().score2 > ans_state.as_ref().unwrap().score2 { ans_state = Some(self.searched_states[i].peek().unwrap().clone()); } } // eprintln!("{}: {}", i + 1, self.states[i].len() + self.searched_states[i].len()); } let ans_state = ans_state.unwrap(); let ans = &ans_state.history; println!("{}", ans.len()); for a in ans { println!("{} {}", a.0 + 1, a.1 + 1); } /* for i in 0..self.n { eprintln!("{}: {:?}", i + 1, ans_state.cards[i]); } */ } } fn main() { let mut buffer = String::new(); io::stdin().read_line(&mut buffer).unwrap(); let n: usize = buffer.trim().parse().unwrap(); let mut cards = vec![]; for _ in 0..n { let mut buffer = String::new(); io::stdin().read_line(&mut buffer).unwrap(); let mut iter = buffer.trim().split_whitespace(); let x: i64 = iter.next().unwrap().parse().unwrap(); let y: i64 = iter.next().unwrap().parse().unwrap(); cards.push((x, y)); } let mut solver = Solver::new(n, cards); solver.solve(); solver.print(); }