結果

問題 No.5017 Tool-assisted Shooting
ユーザー gobi_503gobi_503
提出日時 2023-07-16 18:30:06
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 15,440 bytes
コンパイル時間 1,609 ms
コンパイル使用メモリ 167,940 KB
実行使用メモリ 24,396 KB
スコア 3,057,780
平均クエリ数 1768.18
最終ジャッジ日時 2023-07-16 18:30:31
合計ジャッジ時間 13,927 ms
ジャッジサーバーID
(参考情報)
judge14 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: function `usize_abs` is never used
  --> Main.rs:74:4
   |
74 | fn usize_abs(a: usize, b: usize) -> usize {
   |    ^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: associated function `list` is never used
   --> Main.rs:188:8
    |
188 |     fn list() -> Vec<Self> {
    |        ^^^^

warning: 2 warnings emitted

ソースコード

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

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::Write;
use std::time::SystemTime;
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> IO<R, W> {
IO(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
#[allow(unused_imports)]
use std::io::Write;
self.1.write(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
#[macro_export]
macro_rules! mat {
($($e:expr),*) => { Vec::from(vec![$($e),*]) };
($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}
pub trait SetMinMax {
fn setmin(&mut self, v: Self) -> bool;
fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T
where
T: PartialOrd,
{
fn setmin(&mut self, v: T) -> bool {
*self > v && {
*self = v;
true
}
}
fn setmax(&mut self, v: T) -> bool {
*self < v && {
*self = v;
true
}
}
}
fn usize_abs(a: usize, b: usize) -> usize {
if a > b {
a - b
} else {
b - a
}
}
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Coord {
pub x: isize,
pub y: isize,
}
#[allow(dead_code)]
impl Coord {
pub fn new(p: (isize, isize)) -> Self {
Coord { x: p.0, y: p.1 }
}
pub fn from_usize_pair(p: (usize, usize)) -> Self {
Coord {
x: p.0 as isize,
y: p.1 as isize,
}
}
pub fn in_field(&self) -> bool {
(0 <= self.x && self.x < WIDTH as isize) && (0 <= self.y && self.y < HEIGHT as isize)
}
//
pub fn to_pair(&self) -> (isize, isize) {
(self.x, self.y)
}
pub fn to_usize_pair(&self) -> (usize, usize) {
(self.x as usize, self.y as usize)
}
//
pub fn distance(&self, that: &Self) -> isize {
(self.x - that.x).abs() + (self.y - that.y).abs()
}
pub fn mk_4dir(&self) -> Vec<Self> {
let delta = [(-1, 0), (1, 0), (0, -1), (0, 1)];
delta
.iter()
.map(|&p| self.plus(&Coord::new(p)))
.filter(|&pos| pos.in_field())
.collect()
}
pub fn com_to_delta(com: char) -> Self {
match com {
'U' => Coord::new((0, -1)),
'D' => Coord::new((0, 1)),
'L' => Coord::new((-1, 0)),
'R' => Coord::new((1, 0)),
_ => unreachable!(),
}
}
//
pub fn plus(&self, that: &Self) -> Self {
Coord::new((self.x + that.x, self.y + that.y))
}
pub fn minus(&self, that: &Self) -> Self {
Coord::new((self.x - that.x, self.y - that.y))
}
pub fn access_matrix<'a, T>(&'a self, mat: &'a Vec<Vec<T>>) -> &'a T {
&mat[self.y as usize][self.x as usize]
}
pub fn set_matrix<T>(&self, mat: &mut Vec<Vec<T>>, e: T) {
mat[self.y as usize][self.x as usize] = e;
}
}
// println!("{}")
impl std::fmt::Display for Coord {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "({}, {})", self.x, self.y)?;
Ok(())
}
}
// println!("{:?}")
impl std::fmt::Debug for Coord {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "({}, {})", self.x, self.y)?;
Ok(())
}
}
const WIDTH: usize = 25;
const HEIGHT: usize = 60;
#[allow(dead_code)]
const ENEMY_NUM_MAX: usize = 25;
const MAX_TURN: usize = 1_000;
#[derive(Clone, Copy, Debug, PartialEq)]
enum Command {
Left,
Right,
Stay,
}
impl Command {
fn to_string(&self) -> &str {
match self {
Command::Left => "L",
Command::Right => "R",
Command::Stay => "S",
}
}
fn list() -> Vec<Self> {
vec![Command::Left, Command::Right, Command::Stay]
}
fn move_num(&self) -> usize {
match self {
Command::Left => WIDTH - 1,
Command::Right => 1,
Command::Stay => 0,
}
}
}
#[derive(Clone, Copy, Debug)]
struct Enemy {
hp: usize, // HP (HP)
power: usize, // (100)
x: usize, // x
score: usize, //
}
impl Enemy {
fn new(hp: usize, power: usize, x: usize) -> Self {
Self {
hp,
power,
x,
score: hp,
}
}
}
#[allow(dead_code)]
struct Input {
n: usize,
enemies: Vec<Enemy>,
}
impl Input {
fn new(n: usize, sc: &mut IO<std::io::StdinLock<'_>, std::io::StdoutLock<'_>>) -> Self {
let mut enemies = vec![];
for _ in 0..n {
let v = (0..3).map(|_| sc.read::<usize>()).collect::<Vec<_>>();
let e = Enemy::new(v[0], v[1], v[2]);
enemies.push(e);
}
Self { n, enemies }
}
}
#[derive(Clone, Debug)]
struct State {
me: usize, // x
exp: usize, // 100
turn: usize, //
field: Vec<Vec<Option<Enemy>>>,
score: usize,
}
impl State {
fn new() -> Self {
Self {
me: 12,
exp: 0,
turn: 0,
field: mat![None; HEIGHT; WIDTH],
score: 0,
}
}
fn get_level(&self) -> usize {
1 + self.exp / 100
}
// input
// 1. 1
// 2.
// => isLive
fn update_by_input(&mut self, input: &Input) -> bool {
let mut new_row = vec![None; WIDTH];
for e in input.enemies.iter() {
new_row[e.x] = Some(e.clone());
}
self.field.remove(0);
self.field.push(new_row);
if self.field[0][self.me].is_some() {
eprintln!("Game Over. : {}, : {}", self.turn, self.score);
return false;
}
true
}
//
fn update_by_empty_input(&mut self) -> bool {
let new_row = vec![None; WIDTH];
self.field.remove(0);
self.field.push(new_row);
if self.field[0][self.me].is_some() {
return false;
}
true
}
// 3. 1
// 4.
// => isLive
fn update_by_cmd(&mut self, cmd: &Command) -> bool {
//
self.me = (self.me + cmd.move_num()) % WIDTH;
//
let x = self.me;
if let Some(ene_pos) = self.find_nearest_on_col(x) {
let (_, y) = ene_pos.to_usize_pair();
let mut enemy = self.field[y][x].clone().unwrap();
if enemy.hp <= self.get_level() {
self.score += enemy.score;
self.exp += enemy.power;
self.field[y][x] = None;
} else {
enemy.hp -= self.get_level();
self.field[y][x] = Some(enemy)
}
}
if self.field[0][self.me].is_some() {
return false;
}
true
}
//
fn find_nearest_on_col(&self, x: usize) -> Option<Coord> {
let mut res = None;
for y in 1..HEIGHT {
if self.field[y][x].is_some() {
res = Some(Coord::from_usize_pair((x, y)));
break;
}
}
res
}
/* user define */
// x
fn search_fastest_break(&self, excludes: &Vec<usize>) -> Option<usize> {
let mut row = vec![4242; WIDTH];
let level = self.get_level();
let init_x = self.me;
if let Some(enemy_pos) = self.find_nearest_on_col(init_x) {
let enemy = enemy_pos.access_matrix(&self.field).unwrap();
//
let turn = (enemy.hp + level - 1) / level;
if turn <= enemy_pos.y as usize {
row[init_x] = turn;
}
}
for i in 1..=WIDTH / 2 {
// [, ]
for x in [(init_x + i) % WIDTH, (init_x + WIDTH - i) % WIDTH] {
if excludes.contains(&x) {
continue;
}
if let Some(enemy_pos) = self.find_nearest_on_col(x) {
let enemy = enemy_pos.access_matrix(&self.field).unwrap();
// ((i-1))
let turn = (enemy.hp + level - 1) / level + (i - 1);
if turn <= enemy_pos.y as usize {
row[x] = turn;
}
}
}
}
let mut res = None;
let mut best = 4242;
for x in 0..WIDTH {
if row[x] < best {
res = Some(x);
best = row[x];
}
}
res
}
fn search_better_score(&self, excludes: &Vec<usize>) -> Option<usize> {
let mut row = vec![0.0; WIDTH];
let level = self.get_level();
let init_x = self.me;
if let Some(enemy_pos) = self.find_nearest_on_col(init_x) {
let enemy = enemy_pos.access_matrix(&self.field).unwrap();
//
let turn = (enemy.hp + level - 1) / level;
if turn <= enemy_pos.y as usize {
let rate = enemy.power as f64 / turn as f64;
row[init_x] = rate;
}
}
for i in 1..=WIDTH / 2 {
// [, ]
for x in [(init_x + i) % WIDTH, (init_x + WIDTH - i) % WIDTH] {
if excludes.contains(&x) {
continue;
}
if let Some(enemy_pos) = self.find_nearest_on_col(x) {
let enemy = enemy_pos.access_matrix(&self.field).unwrap();
// ((i-1))
let turn = (enemy.hp + level - 1) / level + (i - 1);
if turn <= enemy_pos.y as usize {
let rate = enemy.power as f64 / turn as f64;
row[x] = rate;
}
}
}
}
let mut res = None;
let mut best = 0.0;
for x in 0..WIDTH {
if row[x] > best {
res = Some(x);
best = row[x];
}
}
res
}
}
fn main() {
let system_time = SystemTime::now();
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
let mut st = State::new();
for turn in 1..=MAX_TURN {
st.turn = turn;
// eprintln!("turn: {}", turn);
/* input & update */
let n: isize = sc.read();
if n == -1 {
break;
}
let n = n as usize;
let input = Input::new(n, &mut sc);
st.update_by_input(&input);
/* solve */
let mut cmd = Command::Stay;
let mut flag = false;
if turn >= 900 {
let mut excledes = vec![];
loop {
if let Some(x) = st.search_better_score(&excledes) {
// x
let offset = (x + WIDTH - st.me) % WIDTH;
if offset == 0 {
cmd = Command::Stay;
} else if offset <= WIDTH / 2 {
cmd = Command::Right;
} else {
cmd = Command::Left;
}
// excludes
if !can_move(st.clone(), x, &cmd) {
excledes.push(x);
} else {
flag = true;
// eprintln!("turn: {}", turn);
break;
}
} else {
break;
}
}
}
if !flag {
let mut excledes = vec![];
loop {
if let Some(x) = st.search_fastest_break(&excledes) {
// x
let offset = (x + WIDTH - st.me) % WIDTH;
if offset == 0 {
cmd = Command::Stay;
} else if offset <= WIDTH / 2 {
cmd = Command::Right;
} else {
cmd = Command::Left;
}
// excludes
if !can_move(st.clone(), x, &cmd) {
excledes.push(x);
} else {
break;
}
} else {
break;
}
}
// stay
if let Some(enemy) = st.field[1][st.me as usize] {
if cmd == Command::Stay {
if enemy.hp > st.get_level() {
cmd = Command::Right;
}
}
}
}
/* output & update */
println!("{}", cmd.to_string());
println!("#{}", cmd.to_string());
st.update_by_cmd(&cmd);
// eprintln!("score {}: {}", turn, st.score);
}
eprintln!("{}ms", system_time.elapsed().unwrap().as_millis());
eprintln!("score: {}", st.score);
}
fn can_move(mut st: State, x: usize, dir: &Command) -> bool {
if *dir == Command::Stay {
return true;
}
while st.me != x {
if !st.update_by_cmd(dir) {
return false;
}
if !st.update_by_empty_input() {
return false;
}
}
true
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0