結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
👑  tipstar0125
|
| 提出日時 | 2023-08-04 18:36:20 |
| 言語 | Rust (1.77.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 11,808 bytes |
| コンパイル時間 | 3,470 ms |
| コンパイル使用メモリ | 169,216 KB |
| 実行使用メモリ | 24,432 KB |
| スコア | 2,007,807 |
| 平均クエリ数 | 928.68 |
| 最終ジャッジ日時 | 2023-08-04 18:39:06 |
| 合計ジャッジ時間 | 164,655 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,659 ms
23,424 KB |
| testcase_01 | AC | 1,641 ms
24,024 KB |
| testcase_02 | AC | 1,597 ms
23,844 KB |
| testcase_03 | AC | 1,658 ms
24,288 KB |
| testcase_04 | AC | 1,599 ms
23,304 KB |
| testcase_05 | AC | 1,610 ms
23,424 KB |
| testcase_06 | AC | 1,638 ms
23,556 KB |
| testcase_07 | AC | 1,613 ms
23,544 KB |
| testcase_08 | AC | 1,593 ms
23,256 KB |
| testcase_09 | AC | 1,622 ms
23,424 KB |
| testcase_10 | AC | 1,630 ms
23,280 KB |
| testcase_11 | AC | 1,624 ms
24,420 KB |
| testcase_12 | AC | 1,603 ms
23,652 KB |
| testcase_13 | AC | 1,664 ms
23,544 KB |
| testcase_14 | AC | 1,677 ms
24,276 KB |
| testcase_15 | AC | 1,600 ms
24,288 KB |
| testcase_16 | AC | 1,636 ms
23,256 KB |
| testcase_17 | AC | 1,670 ms
23,424 KB |
| testcase_18 | AC | 1,566 ms
24,168 KB |
| testcase_19 | AC | 1,653 ms
23,928 KB |
| testcase_20 | AC | 1,665 ms
23,436 KB |
| testcase_21 | AC | 1,651 ms
23,280 KB |
| testcase_22 | AC | 1,574 ms
24,168 KB |
| testcase_23 | AC | 1,647 ms
23,412 KB |
| testcase_24 | AC | 1,655 ms
23,424 KB |
| testcase_25 | AC | 1,655 ms
23,640 KB |
| testcase_26 | AC | 1,517 ms
23,544 KB |
| testcase_27 | AC | 1,596 ms
23,940 KB |
| testcase_28 | AC | 1,633 ms
23,844 KB |
| testcase_29 | AC | 1,518 ms
24,048 KB |
| testcase_30 | AC | 1,604 ms
24,228 KB |
| testcase_31 | AC | 1,588 ms
24,168 KB |
| testcase_32 | AC | 1,668 ms
23,316 KB |
| testcase_33 | RE | - |
| testcase_34 | AC | 1,654 ms
23,556 KB |
| testcase_35 | RE | - |
| testcase_36 | AC | 1,577 ms
23,844 KB |
| testcase_37 | RE | - |
| testcase_38 | AC | 1,662 ms
23,280 KB |
| testcase_39 | AC | 1,625 ms
23,388 KB |
| testcase_40 | AC | 1,449 ms
23,256 KB |
| testcase_41 | AC | 1,634 ms
23,376 KB |
| testcase_42 | AC | 1,617 ms
24,036 KB |
| testcase_43 | AC | 1,620 ms
24,300 KB |
| testcase_44 | AC | 1,696 ms
24,048 KB |
| testcase_45 | RE | - |
| testcase_46 | AC | 1,663 ms
23,268 KB |
| testcase_47 | RE | - |
| testcase_48 | AC | 1,648 ms
24,348 KB |
| testcase_49 | AC | 1,602 ms
24,324 KB |
| testcase_50 | AC | 1,636 ms
23,532 KB |
| testcase_51 | AC | 1,661 ms
23,304 KB |
| testcase_52 | AC | 1,472 ms
23,436 KB |
| testcase_53 | AC | 1,617 ms
23,304 KB |
| testcase_54 | AC | 1,670 ms
23,412 KB |
| testcase_55 | AC | 1,631 ms
23,640 KB |
| testcase_56 | AC | 1,564 ms
23,640 KB |
| testcase_57 | AC | 1,667 ms
24,408 KB |
| testcase_58 | AC | 1,544 ms
23,412 KB |
| testcase_59 | AC | 1,672 ms
24,288 KB |
| testcase_60 | AC | 1,650 ms
24,312 KB |
| testcase_61 | AC | 1,602 ms
24,300 KB |
| testcase_62 | AC | 1,598 ms
24,288 KB |
| testcase_63 | AC | 1,654 ms
23,400 KB |
| testcase_64 | AC | 1,637 ms
23,292 KB |
| testcase_65 | AC | 1,676 ms
23,556 KB |
| testcase_66 | AC | 1,651 ms
23,532 KB |
| testcase_67 | AC | 1,657 ms
24,252 KB |
| testcase_68 | AC | 1,680 ms
23,316 KB |
| testcase_69 | AC | 1,640 ms
24,348 KB |
| testcase_70 | AC | 1,557 ms
23,424 KB |
| testcase_71 | RE | - |
| testcase_72 | AC | 1,604 ms
23,244 KB |
| testcase_73 | AC | 1,676 ms
23,268 KB |
| testcase_74 | AC | 1,576 ms
23,544 KB |
| testcase_75 | AC | 1,598 ms
24,300 KB |
| testcase_76 | AC | 1,646 ms
23,304 KB |
| testcase_77 | AC | 1,627 ms
23,388 KB |
| testcase_78 | AC | 1,680 ms
24,036 KB |
| testcase_79 | RE | - |
| testcase_80 | AC | 1,624 ms
24,048 KB |
| testcase_81 | AC | 1,663 ms
23,736 KB |
| testcase_82 | AC | 1,589 ms
23,940 KB |
| testcase_83 | AC | 1,607 ms
23,940 KB |
| testcase_84 | RE | - |
| testcase_85 | AC | 1,685 ms
23,532 KB |
| testcase_86 | RE | - |
| testcase_87 | AC | 1,583 ms
23,400 KB |
| testcase_88 | AC | 1,629 ms
23,436 KB |
| testcase_89 | AC | 1,620 ms
24,288 KB |
| testcase_90 | AC | 1,690 ms
23,316 KB |
| testcase_91 | AC | 1,689 ms
23,412 KB |
| testcase_92 | AC | 1,580 ms
23,424 KB |
| testcase_93 | RE | - |
| testcase_94 | AC | 1,632 ms
23,268 KB |
| testcase_95 | AC | 1,641 ms
23,940 KB |
| testcase_96 | AC | 1,679 ms
24,252 KB |
| testcase_97 | AC | 1,656 ms
23,544 KB |
| testcase_98 | AC | 1,631 ms
23,904 KB |
| testcase_99 | AC | 1,665 ms
23,424 KB |
コンパイルメッセージ
warning: variable `turn` is assigned to, but never used
--> Main.rs:290:13
|
290 | let mut turn = 0;
| ^^^^
|
= note: consider using `_turn` instead
= note: `#[warn(unused_variables)]` on by default
warning: value assigned to `turn` is never read
--> Main.rs:295:9
|
295 | turn = t + 1;
| ^^^^
|
= help: maybe it is overwritten before being read?
= note: `#[warn(unused_assignments)]` on by default
warning: 2 warnings emitted
ソースコード
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(clippy::type_complexity)]
#![allow(clippy::needless_range_loop)]
#![allow(dead_code)]
use std::{
cmp::Reverse,
collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque},
};
mod rnd {
static mut S: usize = 0;
static MAX: usize = 1e9 as usize;
#[inline]
pub fn init(seed: usize) {
unsafe {
if seed == 0 {
let t = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap()
.as_secs() as usize;
S = t
} else {
S = seed;
}
}
}
#[inline]
pub fn gen() -> usize {
unsafe {
if S == 0 {
init(0);
}
S ^= S << 7;
S ^= S >> 9;
S
}
}
#[inline]
pub fn gen_range(a: usize, b: usize) -> usize {
gen() % (b - a) + a
}
#[inline]
pub fn gen_bool() -> bool {
gen() & 1 == 1
}
#[inline]
pub fn gen_range_isize(a: usize) -> isize {
let mut x = (gen() % a) as isize;
if gen_bool() {
x *= -1;
}
x
}
#[inline]
pub fn gen_range_neg_wrapping(a: usize) -> usize {
let mut x = gen() % a;
if gen_bool() {
x = x.wrapping_neg();
}
x
}
#[inline]
pub fn gen_float() -> f64 {
((gen() % MAX) as f64) / MAX as f64
}
}
#[derive(Debug, Clone)]
struct TimeKeeper {
start_time: std::time::Instant,
time_threshold: f64,
}
impl TimeKeeper {
fn new(time_threshold: f64) -> Self {
TimeKeeper {
start_time: std::time::Instant::now(),
time_threshold,
}
}
#[inline]
fn isTimeOver(&self) -> bool {
let elapsed_time = self.start_time.elapsed().as_nanos() as f64 * 1e-9;
#[cfg(feature = "local")]
{
elapsed_time * 1.5 >= self.time_threshold
}
#[cfg(not(feature = "local"))]
{
elapsed_time >= self.time_threshold
}
}
#[inline]
fn get_time(&self) -> f64 {
let elapsed_time = self.start_time.elapsed().as_nanos() as f64 * 1e-9;
#[cfg(feature = "local")]
{
elapsed_time * 1.5
}
#[cfg(not(feature = "local"))]
{
elapsed_time
}
}
}
const H: usize = 60;
const W: usize = 25;
const TURN: usize = 1000;
const INF: isize = 1 << 60;
#[derive(Debug, Clone, Eq, PartialEq)]
struct Player {
x: usize,
y: usize,
}
impl Player {
fn new() -> Self {
Player { x: 12, y: 0 }
}
fn move_(&mut self, action: isize) {
self.y += 1;
self.x = (W as isize + action + self.x as isize) as usize % W;
}
}
#[derive(Debug, Clone, Eq, PartialEq)]
struct Enemy {
hp: isize,
power: isize,
init_hp: isize,
x: usize,
y: usize,
}
impl Enemy {
fn new(init_hp: isize, power: isize, x: usize, y: usize) -> Self {
Enemy {
hp: init_hp,
power,
init_hp,
x,
y,
}
}
}
#[derive(Debug, Clone, Eq)]
struct State {
player: Player,
S: isize,
score: isize,
damage: isize,
evaluated_score: isize,
enemies: Vec<VecDeque<Enemy>>,
turn: usize,
first_action: isize,
is_dead: bool,
}
impl State {
fn new() -> Self {
State {
player: Player::new(),
S: 0,
score: 0,
damage: 0,
evaluated_score: 0,
enemies: vec![VecDeque::new(); W],
turn: 0,
first_action: 0,
is_dead: false,
}
}
fn update_enemy(&mut self, n: usize) {
let y = H + self.turn;
for _ in 0..n {
let v: Vec<isize> = read_vec();
let h = v[0];
let p = v[1];
let x = v[2] as usize;
let enemy = Enemy::new(h, p, x, y);
self.enemies[x].push_back(enemy);
}
for x in 0..W {
if self.enemies[x].is_empty() {
continue;
}
if y - self.enemies[x][0].y == H {
self.enemies[x].pop_front();
}
}
}
fn get_level(&self) -> isize {
1 + self.S / 100
}
fn advance(&mut self, action: isize) {
self.player.move_(action);
self.attack();
self.turn += 1;
}
fn attack(&mut self) {
if self.enemies[self.player.x].is_empty() {
return;
}
let level = self.get_level();
let enemy = &self.enemies[self.player.x][0];
if enemy.y == self.player.y {
self.is_dead = true;
return;
}
if enemy.y == self.player.y + 1 && enemy.hp > level {
self.is_dead = true;
return;
}
if enemy.hp <= level {
self.score += enemy.init_hp;
self.S += enemy.power;
self.damage += min!(level, enemy.hp);
self.enemies[self.player.x].pop_front();
} else {
self.enemies[self.player.x][0].hp -= level;
self.damage += level;
}
}
fn evaluate_score(&mut self) {
self.evaluated_score = self.S * 1e6 as isize + self.damage;
}
fn is_done(&self) -> bool {
self.turn == TURN
}
fn output(&self, action: isize) {
if action == 0 {
println!("S");
} else if action == -1 {
println!("L");
} else {
println!("R");
}
}
}
impl std::cmp::PartialEq for State {
fn eq(&self, other: &Self) -> bool {
self.evaluated_score == other.evaluated_score
}
}
impl std::cmp::PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
if self.evaluated_score == other.evaluated_score {
Some(std::cmp::Ordering::Equal)
} else if self.evaluated_score > other.evaluated_score {
Some(std::cmp::Ordering::Greater)
} else if self.evaluated_score < other.evaluated_score {
Some(std::cmp::Ordering::Less)
} else {
None
}
}
}
impl std::cmp::Ord for State {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
if self.evaluated_score == other.evaluated_score {
std::cmp::Ordering::Equal
} else if self.evaluated_score > other.evaluated_score {
std::cmp::Ordering::Greater
} else {
std::cmp::Ordering::Less
}
}
}
fn beam_search_action(state: &State, beam_width: usize, time_threshold: f64) -> State {
// let mut now_beam = BinaryHeap::new();
let mut now_beam = BTreeSet::new();
let mut best_state = state;
// now_beam.push(state.clone());
now_beam.insert(state.clone());
let time_keeper = TimeKeeper::new(time_threshold);
let mut turn = 0;
for t in 0.. {
// let mut next_beam = BinaryHeap::new();
let mut next_beam = BTreeSet::new();
turn = t + 1;
let mut now_beam_iter = now_beam.iter();
for _ in 0..beam_width {
// if now_beam.is_empty() {
if now_beam_iter.len() == 0 {
break;
}
// let now_state = now_beam.pop().unwrap();
let now_state = now_beam_iter.next_back().unwrap();
// for action in -1..=1 {
// let mut next_state = now_state.clone();
// if t == 0 {
// next_state.first_action = action;
// next_state.damage = 0;
// }
// next_state.advance(action);
// next_state.evaluate_score();
// if !next_state.is_dead {
// next_beam.push(next_state);
// }
// }
let mut next_state_front = now_state.clone();
let mut next_state_left = now_state.clone();
let mut next_state_right = now_state.clone();
if t == 0 {
next_state_front.first_action = 0;
next_state_front.damage = 0;
next_state_left.first_action = -1;
next_state_left.damage = 0;
next_state_right.first_action = 1;
next_state_right.damage = 0;
}
next_state_front.advance(0);
next_state_front.evaluate_score();
next_state_left.advance(-1);
next_state_left.evaluate_score();
next_state_right.advance(1);
next_state_right.evaluate_score();
if !next_state_front.is_dead {
// next_beam.push(next_state_front);
next_beam.insert(next_state_front);
}
if !next_state_left.is_dead {
// next_beam.push(next_state_left);
next_beam.insert(next_state_left);
}
if !next_state_right.is_dead {
// next_beam.push(next_state_right);
next_beam.insert(next_state_right);
}
if time_keeper.isTimeOver() {
break;
}
}
now_beam = next_beam;
// best_state = now_beam.peek().unwrap();
best_state = now_beam.iter().next_back().unwrap();
if best_state.is_done() || time_keeper.isTimeOver() {
break;
}
}
// eprintln!("{}", turn);
// best_state.first_action
best_state.clone()
}
#[derive(Default)]
struct Solver {}
impl Solver {
fn solve(&mut self) {
let mut state = State::new();
#[cfg(feature = "local")]
{
eprintln!("Local Mode");
let _: Vec<usize> = read_vec();
}
let start = std::time::Instant::now();
let time_threshold = 1.5 * 1e-3; // [sec]
while !state.is_done() {
let N: isize = read();
if N == -1 {
return;
}
state.update_enemy(N as usize);
let s = beam_search_action(&state, 10000, time_threshold);
// if state.turn > 262 {
// eprintln!("{:?}", s.first_action);
// eprintln!("{:?}", s.is_dead);
// }
let action = s.first_action;
state.advance(action);
state.output(action);
}
eprintln!("Score: {}", state.score);
eprintln!("S: {}", state.S);
#[allow(unused_mut, unused_assignments)]
let mut elapsed_time = start.elapsed().as_micros() as f64 * 1e-6;
#[cfg(feature = "local")]
{
eprintln!("Local Mode");
elapsed_time *= 1.5;
}
eprintln!("Elapsed time: {}sec", elapsed_time);
}
}
#[macro_export]
macro_rules! max {
($x: expr) => ($x);
($x: expr, $( $y: expr ),+) => {
std::cmp::max($x, max!($( $y ),+))
}
}
#[macro_export]
macro_rules! min {
($x: expr) => ($x);
($x: expr, $( $y: expr ),+) => {
std::cmp::min($x, min!($( $y ),+))
}
}
fn main() {
std::thread::Builder::new()
.stack_size(128 * 1024 * 1024)
.spawn(|| Solver::default().solve())
.unwrap()
.join()
.unwrap();
}
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}