結果
| 問題 | No.5020 Averaging |
| ユーザー |
 akidai
|
| 提出日時 | 2024-02-25 16:48:04 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,413 bytes |
| コンパイル時間 | 1,371 ms |
| コンパイル使用メモリ | 189,620 KB |
| 実行使用メモリ | 272,000 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2024-02-25 16:49:48 |
| 合計ジャッジ時間 | 57,369 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge10 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
| testcase_31 | TLE | - |
| testcase_32 | TLE | - |
| testcase_33 | TLE | - |
| testcase_34 | TLE | - |
| testcase_35 | TLE | - |
| testcase_36 | TLE | - |
| testcase_37 | TLE | - |
| testcase_38 | TLE | - |
| testcase_39 | TLE | - |
| testcase_40 | TLE | - |
| testcase_41 | TLE | - |
| testcase_42 | TLE | - |
| testcase_43 | TLE | - |
| testcase_44 | TLE | - |
| testcase_45 | TLE | - |
| testcase_46 | TLE | - |
| testcase_47 | TLE | - |
| testcase_48 | TLE | - |
| testcase_49 | TLE | - |
コンパイルメッセージ
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
ソースコード
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() < 950 {
itr += 1;
for i in 0..50 {
if self.time.elapsed().as_millis() >= 950 {
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() >= 950 {
return;
}
}
}
for _ in 0..min(150, new_states.len()) {
let state = new_states.pop().unwrap();
self.states[i + 1].push(state.clone());
}
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();
}