結果
| 問題 | No.5020 Averaging |
| ユーザー |
 akidai
|
| 提出日時 | 2024-02-25 15:51:02 |
| 言語 | Rust (1.77.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,545 bytes |
| コンパイル時間 | 1,665 ms |
| コンパイル使用メモリ | 189,356 KB |
| 実行使用メモリ | 64,000 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2024-02-25 15:52:11 |
| 合計ジャッジ時間 | 52,116 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
コンパイルメッセージ
warning: variable does not need to be mutable --> Main.rs:41:13 | 41 | let mut max_score = 2000000; | ----^^^^^^^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: unused variable: `target` --> Main.rs:79:13 | 79 | 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:80:13 | 80 | let time = Instant::now(); | ^^^^ help: if this is intentional, prefix it with an underscore: `_time` warning: unused variable: `cards` --> Main.rs:93:21 | 93 | let cards = &state.cards; | ^^^^^ help: if this is intentional, prefix it with an underscore: `_cards` warning: 4 warnings emitted
ソースコード
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>>,
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![]);
states[0].push(node);
let time = Instant::now();
Self { n, 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() < 950 {
itr += 1;
for i in 0..50 {
if self.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 best_score = BinaryHeap::new();
for p in 1..n {
self.states[i + 1].push(state.build_next((0, p)));
if self.time.elapsed().as_millis() >= 950 {
break;
}
}
for p in 1..n {
for q in p + 1..n {
let next_state = state.build_next((p, q));
best_score.push(next_state);
if self.time.elapsed().as_millis() >= 950 {
break;
}
}
}
for _ in 0..min(10, best_score.len()) {
self.states[i + 1].push(best_score.pop().unwrap());
}
}
}
}
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();
}