結果
| 問題 | No.5013 セクスタプル (open) |
| ユーザー |
 r3yohei
|
| 提出日時 | 2023-06-05 20:38:49 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 12,100 bytes |
| コンパイル時間 | 2,916 ms |
| コンパイル使用メモリ | 170,024 KB |
| 実行使用メモリ | 4,376 KB |
| スコア | 3,713 |
| 最終ジャッジ日時 | 2023-06-05 20:38:57 |
| 合計ジャッジ時間 | 7,670 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#![allow(non_snake_case, unused)]
use std::io::*;
use std::{collections::*, fmt::format};
use std::{cmp::*, vec};
use crate::input::{*, marker::*};
use crate::rand::Xoshiro256;
const N: usize = 36; // 操作回数
const NUM_DICE: usize = 6; // 操作1回当りのダイスの数
const BOARD_SIZE: usize = 6; // ダイスを配置するセルのサイズ
const TL: f64 = 1.98; // 全体の制限時間
const T0: f64 = 1e5; // 焼きなまし初期温度
const T1: f64 = 1e3; // 焼きなまし終温度
const MULTI_START: f64 = 5.; // 多点スタートする回数
/// proconioみたいなやつ
pub mod input {
use std::{
cell::RefCell,
fmt::Debug,
io::{stdin, BufRead, BufReader, Stdin},
str::{FromStr, SplitWhitespace},
};
thread_local!(
pub static STDIN_SOURCE: RefCell<Source> = RefCell::new(Source {
stdin: BufReader::new(stdin()),
tokens: "".split_whitespace(),
});
);
pub struct Source {
stdin: BufReader<Stdin>,
tokens: SplitWhitespace<'static>,
}
impl Source {
pub fn next_token(&mut self) -> Option<&str> {
self.tokens.next().or_else(|| {
let mut input = String::new();
self.stdin.read_line(&mut input).unwrap();
self.tokens = Box::leak(input.into_boxed_str()).split_whitespace();
self.tokens.next()
})
}
}
#[macro_export]
macro_rules! read_value {
(from $s:expr, [$t:tt; $n:expr]) => {
(0..$n).map(|_| $crate::read_value!(from $s, $t)).collect::<Vec<_>>()
};
(from $s:expr, [$t:tt]) => {
let n = $crate::read_value!(from $s, usize);
$crate::read_value!(from $s, [$t; n])
};
(from $s:expr, $t:ty) => {
<$t as $crate::input::Readable>::read(&mut $s)
};
(from $s:expr, $($t:tt),* $(,)?) => {
($($crate::read_value!(from $s, $t)),*)
};
($($r:tt)*) => {
$crate::input::STDIN_SOURCE.with(|s| {
let mut s = s.borrow_mut();
$crate::read_value!(from s, $($r)*)
})
}
}
#[macro_export]
macro_rules! input {
() => {
};
($x:tt: $t:tt, $($r:tt)*) => {
let $x = $crate::read_value!($t);
$crate::input!($($r)*);
};
(mut $x:tt: $t:tt, $($r:tt)*) => {
let mut $x = $crate::read_value!($t);
$crate::input!($($r)*);
};
(from $s:expr, $x:tt, $t:tt, $($r:tt)*) => {
let $x = $crate::read_value!(from $s, $t);
$crate::input!(from $s, $($r)*);
};
(from $s:expr, mut $x:tt, $t:tt, $($r:tt)*) => {
let mut $x = $crate::read_value!(from $s, $t);
$crate::input!(from $s, $($r)*);
};
($($r:tt)*) => {
$crate::input!($($r)*,);
};
}
pub trait Readable {
type Output;
fn read(source: &mut Source) -> Self::Output;
}
impl<T: FromStr<Err = E>, E: Debug> Readable for T {
type Output = T;
fn read(source: &mut Source) -> T {
source.next_token().unwrap().parse().unwrap()
}
}
pub mod marker {
macro_rules! impl_readable {
($e:ident, $t:ty, $u:ty, $f:expr) => {
pub enum $e {}
impl $crate::input::Readable for $e {
type Output = $t;
fn read(mut source: &mut $crate::input::Source) -> $t {
$f($crate::read_value!(from source, $u))
}
}
};
}
impl_readable!(Usize1, usize, usize, |x| x - 1);
impl_readable!(Isize1, isize, isize, |x| x - 1);
impl_readable!(Chars, Vec<char>, String, |x: String| x.chars().collect());
impl_readable!(Bytes, Vec<u8>, String, |x: String| x.bytes().collect());
}
}
/// 疑似乱数xoshiro256
/// yukicoderでRustのrand crateが使えないため
mod rand {
pub(crate) struct Xoshiro256 {
s0: u64,
s1: u64,
s2: u64,
s3: u64,
}
impl Xoshiro256 {
pub(crate) fn new(mut seed: u64) -> Self {
let s0 = split_mix_64(&mut seed);
let s1 = split_mix_64(&mut seed);
let s2 = split_mix_64(&mut seed);
let s3 = split_mix_64(&mut seed);
Self { s0, s1, s2, s3 }
}
fn next(&mut self) -> u64 {
let result = (self.s1.wrapping_mul(5)).rotate_left(7).wrapping_mul(9);
let t = self.s1 << 17;
self.s2 ^= self.s0;
self.s3 ^= self.s1;
self.s1 ^= self.s2;
self.s0 ^= self.s3;
self.s2 ^= t;
self.s3 = self.s3.rotate_left(45);
result
}
pub(crate) fn gen_usize(&mut self, lower: usize, upper: usize) -> usize {
assert!(lower < upper);
let count = upper - lower;
(self.next() % count as u64) as usize + lower
}
pub(crate) fn gen_i64(&mut self, lower: i64, upper: i64) -> i64 {
assert!(lower < upper);
let count = upper - lower;
(self.next() % count as u64) as i64 + lower
}
pub(crate) fn gen_f64(&mut self) -> f64 {
const UPPER_MASK: u64 = 0x3ff0000000000000;
const LOWER_MASK: u64 = 0xfffffffffffff;
let result = UPPER_MASK | (self.next() & LOWER_MASK);
let result: f64 = unsafe { std::mem::transmute(result) };
result - 1.0
}
pub(crate) fn gen_bool(&mut self, prob: f64) -> bool {
self.gen_f64() < prob
}
}
fn split_mix_64(x: &mut u64) -> u64 {
*x = x.wrapping_add(0x9e3779b97f4a7c15);
let mut z = *x;
z = (z ^ z >> 30).wrapping_mul(0xbf58476d1ce4e5b9);
z = (z ^ z >> 27).wrapping_mul(0x94d049bb133111eb);
z ^ z >> 31
}
}
pub trait ChangeMinMax {
fn change_min(&mut self, v: Self) -> bool;
fn change_max(&mut self, v: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn change_min(&mut self, v: T) -> bool {
*self > v && { *self = v; true }
}
fn change_max(&mut self, v: T) -> bool {
*self < v && { *self = v; true }
}
}
/// 呼び出すたびに現在の経過時間を返す
pub fn get_time() -> f64 {
static mut STIME: f64 = -1.0;
let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
unsafe {
if STIME < 0.0 {
STIME = ms;
}
// ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
#[cfg(feature = "local")]
{
(ms - STIME) * 1.5
}
#[cfg(not(feature = "local"))]
{
(ms - STIME)
}
}
}
/// 入力を受け取って保持するための構造体
#[derive(Clone)]
pub struct Input {
dice: Vec<Vec<usize>>, // dice[i][j] := i回目のダイスjの出目
}
impl Input {
fn new() -> Self {
input! {
dice: [[usize; NUM_DICE]; N],
}
Self { dice }
}
}
/// 6x6のセルの状態を保持するための構造体
#[derive(Clone)]
struct State {
cell: Vec<usize>, // cell[i * BOARD_SIZE + j] := i行j列目に置かれたのが何操作目の出目か
score: i32, // 操作終了後に決まるスコア
}
impl State {
// 構造体とメンバ変数を初期化する
fn new() -> Self {
// どこに何を置くかすべて決まらないとスコアが得られないので，とりあえず置く
let mut cell = vec![];
for i in 0..BOARD_SIZE {
for j in 0..BOARD_SIZE {
cell.push(i * BOARD_SIZE + j);
}
}
// 入力例1の出力を使って，スコア計算の妥当性を確認する用
// let mut cell = vec![0; BOARD_SIZE * BOARD_SIZE];
// for i in 0..N {
// input! {
// xi: Usize1,
// yi: Usize1,
// }
// cell[xi * BOARD_SIZE + yi] = i;
// }
Self {cell, score: 0}
}
// スコアを計算する
fn calc_score(&mut self, input: &Input) {
let mut score = 0;
for i in 0..BOARD_SIZE {
// iを行，jを列とみなすのと，iを列，jを行とみなすのを同時にやる
// iを行とみなすとき，i行目について，全ての列に登場する目があるか･全ての列に登場する目で，さらに追加の目があるかを調べる
let mut num_dice_row = vec![0; NUM_DICE];
let mut forbidden_set_row = HashSet::new();
// iを列とみなすとき，i列目について，全ての行に登場する目があるか･全ての行に登場する目で，さらに追加の目があるかを調べる
let mut num_dice_col = vec![0; NUM_DICE];
let mut forbidden_set_col = HashSet::new();
for j in 0..BOARD_SIZE {
// iを行とみなすとき
let dice_ij = &input.dice[self.cell[i * BOARD_SIZE + j]];
let mut num_dice_map_row = HashMap::new();
for &d in dice_ij {
*num_dice_map_row.entry(d).or_insert(0) += 1;
}
// セル(i, j)について計上
for d in 1..=6 {
// (i, j)に存在しない目があるかどうかを判定しておく
if let Some(&num_d) = num_dice_map_row.get(&d) {
// あればとりあえず計上
num_dice_row[d - 1] += num_d;
} else {
// なければ無いことを記録
forbidden_set_row.insert(d);
}
}
// iを列とみなすとき
let dice_ji = &input.dice[self.cell[j * BOARD_SIZE + i]];
let mut num_dice_map_col = HashMap::new();
for &d in dice_ji {
*num_dice_map_col.entry(d).or_insert(0) += 1;
}
// セル(i, j)について計上
for d in 1..=6 {
// (i, j)に存在しない目があるかどうかを判定しておく
if let Some(&num_d) = num_dice_map_col.get(&d) {
// あればとりあえず計上
num_dice_col[d - 1] += num_d;
} else {
// なければ無いことを記録
forbidden_set_col.insert(d);
}
}
}
// iを行とみなすとき，各目1~6で，すべての列に含まれるものの数を数え，定義よりその数-3が当該行のスコアとなる
// iを列とみなすときも同じ
for d in 1..=6 {
if !forbidden_set_row.contains(&d) {score += num_dice_row[d - 1] - 3;}
if !forbidden_set_col.contains(&d) {score += num_dice_col[d - 1] - 3;}
}
}
self.score = score;
}
// 回答を出力する
fn print(&self) {
// cell[i * BOARD_SIZE + j] = 何番目の操作か なのだから，cellをargsortして出力すれば良い
let mut index = (0..N).collect::<Vec<_>>();
// 昇順ソート
index.sort_by(|&i, &j| self.cell[i].cmp(&self.cell[j]));
// 1-indexに直しつつ出力
for &i in &index {
println!("{} {}", i / BOARD_SIZE + 1, i % BOARD_SIZE + 1);
}
}
}
fn main() {
get_time();
let input = Input::new();
let mut state = State::new();
state.calc_score(&input);
state.print();
eprintln!("score: {}", state.score);
eprintln!("time: {}", get_time());
}