結果
問題 | No.1079 まお |
ユーザー | akakimidori |
提出日時 | 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 |
ソースコード
// ---------- 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();}