結果
| 問題 | No.515 典型LCP |
| ユーザー |
 tubo28
|
| 提出日時 | 2017-06-06 12:36:12 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,667 bytes |
| コンパイル時間 | 14,326 ms |
| コンパイル使用メモリ | 401,444 KB |
| 実行使用メモリ | 712,412 KB |
| 最終ジャッジ日時 | 2024-09-22 11:44:14 |
| 合計ジャッジ時間 | 24,110 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | AC | 140 ms
71,368 KB |
| testcase_02 | AC | 88 ms
65,288 KB |
| testcase_03 | AC | 6 ms
14,396 KB |
| testcase_04 | AC | 6 ms
14,456 KB |
| testcase_05 | TLE | - |
| testcase_06 | MLE | - |
| testcase_07 | MLE | - |
| testcase_08 | MLE | - |
| testcase_09 | AC | 85 ms
65,364 KB |
| testcase_10 | AC | 87 ms
65,408 KB |
| testcase_11 | AC | 85 ms
65,500 KB |
| testcase_12 | AC | 84 ms
65,452 KB |
| testcase_13 | AC | 117 ms
76,836 KB |
| testcase_14 | AC | 77 ms
45,776 KB |
| testcase_15 | TLE | - |
| testcase_16 | MLE | - |
コンパイルメッセージ
warning: field `n` is never read
--> src/main.rs:356:5
|
355 | struct SparceTable<T> {
| ----------- field in this struct
356 | n: usize,
| ^
|
= note: `#[warn(dead_code)]` on by default
ソースコード
// パフォーマスと使いやすさ再優先のためunsafeもunwrapもカジュアルに使う．
// 入力はASCII文字以外ダメ．
fn main() {
let mut input_buffer = String::with_capacity(cp_io::BUFFER_SIZE);
let mut output_buffer = Vec::with_capacity(cp_io::BUFFER_SIZE);
unsafe {
cp_io::input::buf = &mut output_buffer;
cp_io::output::buf = &mut input_buffer;
}
std::thread::Builder::new()
.stack_size(104_857_600)
.spawn(solve).unwrap()
.join().unwrap();
cp_io::output::flush();
}
#[macro_use]
#[allow(dead_code, non_upper_case_globals, unused_macros)]
mod cp_io {
pub const BUFFER_SIZE: usize = 8192;
#[macro_use]
pub mod output {
pub const ENABLE_DUMP: bool = true;
pub const PRECISION: usize = 10;
pub static mut buf: *mut String = 0 as *mut String;
macro_rules! p {
($x: expr) => {{
$x.output();
"\n".output();
unsafe {
if (*cp_io::output::buf).len() > cp_io::BUFFER_SIZE {
flush();
}
}
}};
($x: expr, $($y: expr),+) => {{
$x.output();
" ".output();
p!($($y),+);
}};
}
macro_rules! pf {
($($x: expr),+) => {{
p!($($x),+);
flush();
}};
}
macro_rules! d {
($($a: expr),+) => {
if ENABLE_DUMP {
use std::io::*;
write!(stderr(), "{}:{}\t", file!(), line!()).unwrap();
d!(A $($a),+);
write!(stderr(), " = ").unwrap();
d!(B $($a),+);
write!(stderr(), "\n").unwrap();
stderr().flush().unwrap();
}
};
(A $x: expr) => {
write!(stderr(), "{}", stringify!($x)).unwrap();
};
(A $x: expr, $($y: expr),+) => {
write!(stderr(), "{}, ", stringify!($x)).unwrap();
d!(A $($y),+);
};
(B $x: expr) => {
write!(stderr(), "{:?}", $x).unwrap();
};
(B $x: expr, $($y: expr),+) => {
write!(stderr(), "{:?}, ", $x).unwrap();
d!(B $($y),+);
};
}
pub trait Output {
fn output(&self);
}
macro_rules! output_normal {
($t: ty) => {
impl Output for $t {
fn output(&self) {
unsafe {
use std::fmt::Write;
write!(&mut *buf, "{}", self).unwrap();
}
}
}
};
($t: ty, $($u: ty),+) => {
output_normal!($t);
output_normal!($($u),+);
};
}
macro_rules! output_float {
($t: ty) => {
impl Output for $t {
fn output(&self) {
unsafe {
use std::fmt::Write;
write!(&mut *buf, "{:.*}", PRECISION, self).unwrap();
}
}
}
};
($t: ty, $($u: ty),+) => {
output_float!($t);
output_float!($($u),+);
};
}
pub fn flush() {
unsafe {
print!("{}", *buf);
use std::io::*;
stdout().flush().unwrap();
(*buf).clear();
}
}
output_normal!(u8, u16, u32, u64, usize);
output_normal!(i8, i16, i32, i64, isize);
output_normal!(bool, &'static str, String);
output_float!(f32, f64);
}
pub mod input {
pub trait Input<T> {
fn input() -> T;
}
macro_rules! input_primitive {
($t: ty) => {
impl Input<$t> for $t {
fn input() -> $t {
get_word().expect("EOF?").parse()
.unwrap_or_else(|e| panic!("Cannot parse {}", e))
}
}
};
($t: ty, $($u: ty),+) => {
input_primitive!($t);
input_primitive!($($u),+);
};
}
macro_rules! input_tuple {
($($t: ident),*) => {
impl< $($t: Input<$t>),* > Input< ( $($t),* ) > for ( $($t),* ) {
fn input() -> ( $($t),* ) {
( $( $t::input()),* )
}
}
};
}
input_primitive!(u8, u16, u32, u64, usize);
input_primitive!(i8, i16, i32, i64, isize);
input_primitive!(bool, String);
input_tuple!(A, B);
input_tuple!(A, B, C);
input_tuple!(A, B, C, D);
pub fn get<T: Input<T>>() -> T {
T::input()
}
pub fn get_vec<T: Input<T>>(n: usize) -> Vec<T> {
(0..n).map(|_| get()).collect()
}
pub fn get_mat<T: Input<T>>(r: usize, c: usize) -> Vec<Vec<T>> {
(0..r).map(|_| get_vec(c)).collect()
}
pub fn get_vec_char() -> Vec<char> {
get_word().unwrap().chars().collect()
}
pub fn get_mat_char(h: usize) -> Vec<Vec<char>> {
(0..h).map(|_| get_vec_char()).collect()
}
pub fn get_line() -> String {
get_line_wrapped().unwrap()
}
fn get_word() -> Option<String> {
let mut res = String::with_capacity(18);
while let Some(c) = get_u8() {
let d = c as char;
if !d.is_whitespace() {
res.push(d);
} else if res.len() != 0 {
unget_u8(c);
break;
}
}
if res.len() == 0 { None } else { Some(res) }
}
fn get_line_wrapped() -> Option<String> {
let c = get_u8();
if c.is_none() {
return None;
}
let mut line = String::with_capacity(18);
line.push(c.unwrap() as char);
loop {
let c = get_u8();
if c.is_none() || c.unwrap() == b'\n' {
// コメントはC++等での仕様
// if c.is_some() {
// self.unget_u8(b'\n');
// }
return Some(line);
}
line.push(c.unwrap() as char);
}
}
pub fn has_next() -> bool {
loop {
let c = get_u8();
if c.is_none() {
return false;
}
let c = c.unwrap();
if !(c as char).is_whitespace() {
unget_u8(c);
return true;
}
}
}
pub static mut buf: *mut Vec<u8> = 0 as *mut Vec<u8>;
fn get_u8() -> Option<u8> {
unsafe {
let b = &mut (*buf);
use std::io::{stdin, Read};
if let Some(c) = b.pop() {
Some(c as u8)
} else {
b.resize(super::BUFFER_SIZE, 0);
match stdin().read(b) {
Ok(l) if l > 0 => {
b.truncate(l);
b.reverse();
b.pop()
}
_ => return None,
}
}
}
}
fn unget_u8(c: u8) {
unsafe {
(*buf).push(c)
}
}
}
}
#[allow(unused_imports)]
use cp_io::input::*;
#[allow(unused_imports)]
use cp_io::output::*;
use std::*;
use std::collections::*;
use std::mem::swap;
use std::fmt::*;
use std::cmp::*;
struct Node {
depth: usize,
next: Vec<Option<*mut Node>>,
}
impl Node {
fn new(depth: usize) -> Node {
let n = vec![None; 26];
Node {
depth: depth,
next: n,
}
}
fn insert<'a, I>(&'a mut self, it: I) -> *const Node
where I: IntoIterator<Item=&'a u8>
{
let mut it = it.into_iter();
if let Some(c) = it.next() {
let d = self.depth;
if self.next[*c as usize].is_none() {
let p = Box::into_raw(Box::new(Self::new(d + 1)));
self.next[*c as usize] = Some(p);
}
unsafe {
(*self.next[*c as usize].unwrap()).insert(it)
}
} else {
self
}
}
}
struct Trie {
root: *mut Node,
}
impl Trie {
fn new() -> Self {
Trie {
root: Box::into_raw(Box::new(Node::new(0))),
}
}
fn insert<'a, I>(&'a mut self, it: I) -> *const Node
where I: IntoIterator<Item=&'a u8>
{
unsafe {
(*self.root).insert(it)
}
}
fn dfs(n: *const Node, a: &mut Vec<*const Node>) {
// d!(n);
a.push(n);
unsafe {
for p in &(*n).next {
if let &Some(c) = p {
Self::dfs(c, a);
a.push(n);
// d!(c);
}
}
}
// d!(n);
}
fn make_array(&self) -> Vec<*const Node> {
let mut a = vec![];
Trie::dfs(self.root, &mut a);
a
}
}
struct SparceTable<T> {
n: usize,
min: Vec<Vec<T>>,
log2: Vec<usize>,
}
impl<T: Copy + Ord + Debug> SparceTable<T> {
fn new<I>(it: I) -> SparceTable<T>
where I: IntoIterator<Item=T> {
let it = it.into_iter();
let v = it.collect::<Vec<_>>();
let n = v.len();
let mut log2 = vec![0; 800000*2 + 1];
log2[1] = 0;
for i in 2..log2.len() {
log2[i] = log2[i/2] + 1;
}
let mut res = SparceTable {
n: n,
min: vec![v],
log2: log2,
};
for i in 0..30 {
let w = 1 << i;
if n < w*2-1 {
break;
}
let next = (0..n-w*2-1).map(|l| {
min(res.min[i][l], res.min[i][l + w])
}).collect();
res.min.push(next);
}
res
}
fn rmq(&self, l: usize, r: usize) -> T {
let w = r - l;
// let mut i = 0;
// while (1 << i) < w {
// i += 1;
// }
// i -= 1;
let i = self.log2[w];
let rr = r - (1 << i);
//assert!(r - (1 << i) == rr);
min(self.min[i][l], self.min[i][rr])
}
}
fn solve() {
while has_next() {
let n = get();
let s: Vec<Vec<u8>> = get_mat_char(n)
.iter().map(|s| s.iter().map(|&c| c as u8 - b'a').collect())
.collect();
// d!(s);
let (m, mut x, d): (usize, u64, u64) = get();
let mut i = vec![0usize; m];
let mut j = vec![0usize; m];
for k in 0..m {
let n = n as u64;
i[k] = ((x / (n - 1)) + 1) as usize;
j[k] = ((x % (n - 1)) + 1) as usize;
if i[k] > j[k] {
swap(&mut i[k], &mut j[k]);
} else {
j[k] = j[k] + 1;
}
x = (x + d) % (n * (n - 1));
}
let mut trie = Trie::new();
let (index, depth) = {
let node = s.iter().map(|s| trie.insert(s.iter())).collect::<Vec<_>>();
let pa = trie.make_array();
let mut mp = BTreeMap::<_, usize>::new();
for i in 0..pa.len() {
mp.entry(pa[i]).or_insert(i);
}
let index = (0..n).map(|i| mp[&node[i]]).collect::<Vec<usize>>();
let da = pa.iter().map(|i| unsafe { (**i).depth }).collect::<Vec<usize>>();
(index, da)
};
let rmq = SparceTable::<_>::new(depth.iter());
let calc = |i: usize, j: usize| {
let (l, r) = if index[i] < index[j] {
(index[i], index[j])
} else {
(index[j], index[i])
};
rmq.rmq(l, r + 1)
};
let ans = i.iter().zip(j.iter()).fold(0, |acc, (&i, &j)| {
acc + calc(i - 1, j - 1)
});
p!(ans);
}
}