結果

問題 No.5020 Averaging
コンテスト
ユーザー akidai
提出日時 2024-02-25 15:31:10
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 5,649 bytes
コンパイル時間 2,183 ms
コンパイル使用メモリ 190,688 KB
実行使用メモリ 695,040 KB
スコア 0
最終ジャッジ日時 2024-02-25 15:32:10
合計ジャッジ時間 59,463 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 49 MLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `min`
 --> Main.rs:1:21
  |
1 | use std::cmp::{max, min};
  |                     ^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: variable does not need to be mutable
  --> Main.rs:40:13
   |
40 |         let mut max_score = 2000000;
   |             ----^^^^^^^^^
   |             |
   |             help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: unused variable: `target`
  --> Main.rs:76:13
   |
76 |         let target = 10_i64.pow(17) * 5;
   |             ^^^^^^ help: if this is intentional, prefix it with an underscore: `_target`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `cards`
  --> Main.rs:90:21
   |
90 |                 let cards = &state.cards;
   |                     ^^^^^ help: if this is intentional, prefix it with an underscore: `_cards`

warning: 4 warnings emitted

ソースコード

diff # 

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,
    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<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Node {
    fn new(cards: Vec<(i64, i64)>, history: Vec<(usize, usize)>) -> Self {
        let score = Node::calc_score(&cards);
        Self {
            cards,
            score,
            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 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);
        Self::new(cards, history)
    }
}

struct Solver {
    n: usize,
    states: Vec<BinaryHeap<Node>>,
}

impl Solver {
    fn new(n: usize, cards: Vec<(i64, i64)>) -> Self {
        let mut states = vec![BinaryHeap::new(); 51];
        let node = Node::new(cards, vec![]);
        states[0].push(node);
        Self { n, states }
    }

    fn solve(&mut self) {
        let n = self.n;
        let target = 10_i64.pow(17) * 5;
        let time = Instant::now();
        let mut itr = 0;
        while time.elapsed().as_millis() < 950 {
            itr += 1;
            for i in 0..50 {
                if time.elapsed().as_millis() >= 950 {
                    break;
                }
                let state = &self.states[i].pop();
                if state.is_none() {
                    continue;
                }
                let state = state.as_ref().unwrap();
                let cards = &state.cards;
                println!("{}: {}", itr, i + 1);
                /*
                let mut cur_diff = max((cards[0].0 - target).abs(), (cards[0].1 - target).abs());
                let mut tmp = (n, n);
                */
                for p in 1..n {
                    /*
                    let new_card_0 = ((cards[p].0 + cards[0].0) / 2, (cards[p].1 + cards[0].1) / 2);
                    let new_diff = max((new_card_0.0 - target).abs(), (new_card_0.1 - target).abs());
                    if new_diff < cur_diff {
                        cur_diff = new_diff;
                        tmp = (0, p);
                    }
                    */
                    self.states[i + 1].push(state.build_next((0, p)));
                }
                /*
                let mut best_new_diff = 10_i64.pow(17) * 5;
                let mut spare = (n, n);
                if i < 49 {
                    for p in 1..n {
                        for q in p + 1..n {
                            let new_card = ((self.cards[p].0 + self.cards[q].0) / 2, (self.cards[p].1 + self.cards[q].1) / 2);

                            let new_card_0 = ((self.cards[0].0 + new_card.0) / 2, (self.cards[0].1 + new_card.1) / 2);
                            let new_diff = max((new_card_0.0 - self.target).abs(), (new_card_0.1 - self.target).abs());
                            if new_diff < cur_diff {
                                cur_diff = new_diff;
                                tmp = (p, q);
                            }
                            if new_diff < best_new_diff {
                                best_new_diff = new_diff;
                                spare = (p, q);
                            }
                        }
                    }
                }
                */
                for p in 1..n {
                    for q in p + 1..n {
                        self.states[i + 1].push(state.build_next((p, q)));
                    }
                }
                eprintln!("{}: {}", i + 1, self.states[i + 1].peek().unwrap().score);
            }
        }
    }

    fn print(&self) {
        let ans_state = self.states[50].peek().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();
}
0