結果

問題 No.1079 まお
ユーザー akakimidoriakakimidori
提出日時 2021-10-14 10:16:09
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 2,816 bytes
コンパイル時間 13,019 ms
コンパイル使用メモリ 380,500 KB
実行使用メモリ 7,492 KB
最終ジャッジ日時 2024-09-17 16:30:27
合計ジャッジ時間 15,164 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 27 ms
6,940 KB
testcase_13 AC 31 ms
6,944 KB
testcase_14 AC 35 ms
6,944 KB
testcase_15 AC 44 ms
6,940 KB
testcase_16 AC 48 ms
6,944 KB
testcase_17 AC 53 ms
6,940 KB
testcase_18 AC 51 ms
6,944 KB
testcase_19 AC 50 ms
6,944 KB
testcase_20 AC 49 ms
6,940 KB
testcase_21 AC 47 ms
6,944 KB
testcase_22 AC 51 ms
6,980 KB
testcase_23 AC 51 ms
6,940 KB
testcase_24 AC 52 ms
7,236 KB
testcase_25 AC 53 ms
7,488 KB
testcase_26 AC 56 ms
7,492 KB
testcase_27 AC 13 ms
6,940 KB
testcase_28 AC 29 ms
6,940 KB
testcase_29 AC 25 ms
6,944 KB
testcase_30 AC 26 ms
6,940 KB
testcase_31 AC 24 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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

// ---------- begin init array ----------
pub struct InitArray<T> {
data: Vec<T>,
used: Vec<bool>,
list: Vec<usize>,
zero: T,
}
impl<T: Copy> InitArray<T> {
pub fn new(size: usize, zero: T) -> Self {
InitArray {
data: vec![zero; size],
used: vec![false; size],
list: vec![],
zero: zero,
}
}
pub fn init(&mut self) {
for x in self.list.drain(..) {
self.used[x] = false;
self.data[x] = self.zero;
}
}
}
impl<T> std::ops::Index<usize> for InitArray<T> {
type Output = T;
fn index(&self, pos: usize) -> &Self::Output {
&self.data[pos]
}
}
impl<T> std::ops::IndexMut<usize> for InitArray<T> {
fn index_mut(&mut self, pos: usize) -> &mut Self::Output {
if !self.used[pos] {
self.used[pos] = true;
self.list.push(pos);
}
&mut self.data[pos]
}
}
// ---------- end init array ----------
fn read() -> (i32, Vec<i32>) {
let mut s = String::new();
use std::io::Read;
std::io::stdin().read_to_string(&mut s).unwrap();
let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::<i32>());
let mut next = || it.next().unwrap();
let n = next();
let k = next();
(k, (0..n).map(|_| next()).collect())
}
fn run() {
let (k, a) = read();
let mut z = a.clone();
z.extend(a.iter().map(|a| k - *a));
z.sort();
z.dedup();
let mut a = a.iter().map(|a| z.binary_search(a).unwrap()).collect::<Vec<_>>();
let mut map = InitArray::new(z.len(), (0usize, 0usize));
let mut calc = |l: &[usize], r: &[usize]| -> usize {
map.init();
let mut min = z.len();
let mut cnt = 0;
let mut x = 0;
let mut ans = 0;
for (i, &r) in r.iter().enumerate() {
if min > r {
min = r;
cnt = 1;
} else if min == r {
cnt += 1;
}
while l.get(x).map_or(false, |l| *l > min) {
let po = &mut map[l[x]];
po.0 += 1;
po.1 += x + 1;
x += 1;
}
if cnt == 1 {
let po = map[z.len() - 1 - r];
ans += po.0 * (i + 1) + po.1;
}
}
ans
};
let mut ans = 0;
let mut dfs = vec![a.as_mut_slice()];
while let Some(a) = dfs.pop() {
if a.len() == 1 {
if a[0] == z.len() - 1 - a[0] {
ans += 1;
}
continue;
}
let m = a.len() / 2;
let (l, r) = a.split_at_mut(m);
l.reverse();
ans += calc(l, r) + calc(r, l);
dfs.push(l);
dfs.push(r);
}
println!("{}", ans);
}
fn main() {
run();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0