結果

問題 No.5020 Averaging
ユーザー xyz600600
提出日時 2024-02-25 14:17:01
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 22 ms / 1,000 ms
コード長 4,829 bytes
コンパイル時間 1,445 ms
コンパイル使用メモリ 191,684 KB
実行使用メモリ 6,676 KB
スコア 28,639,184
最終ジャッジ日時 2024-02-25 14:17:16
合計ジャッジ時間 3,784 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `problem`
  --> Main.rs:90:25
   |
90 | fn simulate_with_greedy(problem: &Problem, state: &mut State, turn: usize) -> u64 {
   |                         ^^^^^^^ help: if this is intentional, prefix it with an underscore: `_problem`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: 1 warning emitted

ソースコード

diff #
プレゼンテーションモードにする

use std::io;
#[derive(Clone, Copy)]
struct Card {
number: [u64; 2],
}
struct Problem {
cards: Vec<Card>,
operation_count: usize,
}
fn read_problem() -> Problem {
//
let mut input = String::new();
// N
io::stdin().read_line(&mut input).expect("Failed to read line");
let n: usize = input.trim().parse().expect("Input was not a number");
// A_i, B_i
let mut pairs = Vec::new(); // (A_i, B_i)
for _ in 0..n {
input.clear(); //
io::stdin().read_line(&mut input).expect("Failed to read line");
// u64
let parts: Vec<u64> = input
.trim()
.split_whitespace()
.map(|x| x.parse().expect("Input was not a number"))
.collect();
if parts.len() != 2 {
eprintln!("Invalid input format");
continue;
}
//
pairs.push((parts[0], parts[1]));
}
let cards = pairs
.into_iter()
.map(|(v1, v2)| Card { number: [v1, v2] })
.collect::<Vec<_>>();
Problem {
cards,
operation_count: 50,
}
}
#[derive(Clone)]
struct State {
card_pool: Vec<Card>,
}
const TARGET_VALUE: u64 = 50_0000_0000_0000_0000;
impl State {
fn new(problem: &Problem) -> State {
State {
card_pool: problem.cards.clone(),
}
}
fn copy_from(&mut self, state: &State) {
for i in 0..state.card_pool.len() {
self.card_pool[i] = state.card_pool[i]
}
}
fn manipulate(&mut self, c1: usize, c2: usize) {
let first = (self.card_pool[c1].number[0] + self.card_pool[c2].number[0]) / 2;
let second = (self.card_pool[c1].number[1] + self.card_pool[c2].number[1]) / 2;
self.card_pool[c1].number[0] = first;
self.card_pool[c2].number[0] = first;
self.card_pool[c1].number[1] = second;
self.card_pool[c2].number[1] = second;
}
}
fn calculate_cost_diff(first: u64, second: u64) -> u64 {
first.abs_diff(TARGET_VALUE).max(second.abs_diff(TARGET_VALUE))
}
fn simulate_with_greedy(problem: &Problem, state: &mut State, turn: usize) -> u64 {
let mut state = state.clone();
for _iter in 0..turn {
//
let mut best_improve_pair = (0, 0);
let mut best_gain = std::i64::MIN;
let c1 = 0;
for c2 in c1 + 1..state.card_pool.len() {
let first = (state.card_pool[c1].number[0] + state.card_pool[c2].number[0]) / 2;
let second = (state.card_pool[c1].number[1] + state.card_pool[c2].number[1]) / 2;
let before_c1_diff = calculate_cost_diff(state.card_pool[c1].number[0], state.card_pool[c1].number[1]);
let before_c2_diff = calculate_cost_diff(state.card_pool[c2].number[0], state.card_pool[c2].number[1]);
let before_diff = before_c1_diff + before_c2_diff;
let after_diff = calculate_cost_diff(first, second) * 2;
let gain = before_diff as i64 - after_diff as i64;
if best_gain < gain {
best_gain = gain;
best_improve_pair = (c1, c2);
}
}
let (c1, c2) = best_improve_pair;
state.manipulate(c1, c2);
}
// calculate score
// ⌊2000000−100000 log 10 (max(V_1 ,V_2)+1)⌋
let diff = calculate_cost_diff(state.card_pool[0].number[0], state.card_pool[0].number[1]);
(200_0000f64 - 10_0000f64 * (diff as f64).log10()).floor() as u64
}
fn solve(problem: &Problem) -> Vec<(usize, usize)> {
let mut state = State::new(problem);
let mut init_state = State::new(problem);
let mut ret = vec![];
for turn in 1..=problem.operation_count {
//
let mut best_improve_pair = (0, 0);
let mut best_score = std::u64::MIN;
let c1 = 0;
for c2 in c1 + 1..state.card_pool.len() {
init_state.copy_from(&state);
init_state.manipulate(c1, c2);
let score = simulate_with_greedy(problem, &mut init_state, problem.operation_count - turn);
if best_score < score {
best_score = score;
best_improve_pair = (c1, c2);
}
}
let (c1, c2) = best_improve_pair;
state.manipulate(c1, c2);
ret.push((c1 + 1, c2 + 1));
}
ret
}
fn main() {
let problem = read_problem();
let ret = solve(&problem);
println!("{}", ret.len());
for (c1, c2) in ret.iter() {
println!("{} {}", c1, c2);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0