結果

問題 No.5020 Averaging
ユーザー akidaiakidai
提出日時 2024-02-25 16:53:11
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 978 ms / 1,000 ms
コード長 6,572 bytes
コンパイル時間 1,199 ms
コンパイル使用メモリ 189,308 KB
実行使用メモリ 194,944 KB
スコア 23,480,204
最終ジャッジ日時 2024-02-25 16:55:39
合計ジャッジ時間 52,139 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 962 ms
173,056 KB
testcase_01 AC 961 ms
184,960 KB
testcase_02 AC 960 ms
177,536 KB
testcase_03 AC 962 ms
181,760 KB
testcase_04 AC 964 ms
176,640 KB
testcase_05 AC 963 ms
182,912 KB
testcase_06 AC 968 ms
178,944 KB
testcase_07 AC 969 ms
184,960 KB
testcase_08 AC 974 ms
178,560 KB
testcase_09 AC 961 ms
182,784 KB
testcase_10 AC 963 ms
179,072 KB
testcase_11 AC 965 ms
184,832 KB
testcase_12 AC 963 ms
177,408 KB
testcase_13 AC 978 ms
184,832 KB
testcase_14 AC 967 ms
178,048 KB
testcase_15 AC 964 ms
179,068 KB
testcase_16 AC 968 ms
177,920 KB
testcase_17 AC 961 ms
176,384 KB
testcase_18 AC 960 ms
183,552 KB
testcase_19 AC 968 ms
168,064 KB
testcase_20 AC 962 ms
177,024 KB
testcase_21 AC 961 ms
185,088 KB
testcase_22 AC 959 ms
78,720 KB
testcase_23 AC 958 ms
80,640 KB
testcase_24 AC 965 ms
81,152 KB
testcase_25 AC 942 ms
80,384 KB
testcase_26 AC 955 ms
176,512 KB
testcase_27 AC 973 ms
176,640 KB
testcase_28 AC 962 ms
178,816 KB
testcase_29 AC 964 ms
173,568 KB
testcase_30 AC 965 ms
177,024 KB
testcase_31 AC 968 ms
174,976 KB
testcase_32 AC 963 ms
167,040 KB
testcase_33 AC 965 ms
183,808 KB
testcase_34 AC 960 ms
177,280 KB
testcase_35 AC 963 ms
174,592 KB
testcase_36 AC 968 ms
194,944 KB
testcase_37 AC 965 ms
174,848 KB
testcase_38 AC 965 ms
182,272 KB
testcase_39 AC 963 ms
180,608 KB
testcase_40 AC 963 ms
178,816 KB
testcase_41 AC 954 ms
177,152 KB
testcase_42 AC 964 ms
181,376 KB
testcase_43 AC 963 ms
184,576 KB
testcase_44 AC 964 ms
177,024 KB
testcase_45 AC 962 ms
177,664 KB
testcase_46 AC 965 ms
178,944 KB
testcase_47 AC 962 ms
185,088 KB
testcase_48 AC 974 ms
181,376 KB
testcase_49 AC 963 ms
178,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> Main.rs:47:13
   |
47 |         let mut max_score = 2000000;
   |             ----^^^^^^^^^
   |             |
   |             help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
  --> Main.rs:58:13
   |
58 |         let mut max_score = 2000000;
   |             ----^^^^^^^^^
   |             |
   |             help: remove this `mut`

warning: variable does not need to be mutable
  --> Main.rs:95:13
   |
95 |         let mut searched_states = vec![BinaryHeap::new(); 51];
   |             ----^^^^^^^^^^^^^^^
   |             |
   |             help: remove this `mut`

warning: unused variable: `target`
   --> Main.rs:102:13
    |
102 |         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: `time`
   --> Main.rs:103:13
    |
103 |         let time = Instant::now();
    |             ^^^^ help: if this is intentional, prefix it with an underscore: `_time`

warning: variable `itr` is assigned to, but never used
   --> Main.rs:104:17
    |
104 |         let mut itr = 0;
    |                 ^^^
    |
    = note: consider using `_itr` instead

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

warning: 7 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,
    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<std::cmp::Ordering> {
        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<BinaryHeap<Node>>,
    searched_states: Vec<BinaryHeap<Node>>,
    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();
}
0