結果
問題 | No.1209 XOR Into You |
ユーザー | cotton_fn_ |
提出日時 | 2020-11-07 04:54:06 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 7,373 bytes |
コンパイル時間 | 15,764 ms |
コンパイル使用メモリ | 400,616 KB |
実行使用メモリ | 8,284 KB |
最終ジャッジ日時 | 2024-07-22 14:18:34 |
合計ジャッジ時間 | 19,364 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 7 ms
6,944 KB |
testcase_05 | AC | 6 ms
6,940 KB |
testcase_06 | AC | 39 ms
6,940 KB |
testcase_07 | AC | 49 ms
7,124 KB |
testcase_08 | AC | 42 ms
6,944 KB |
testcase_09 | AC | 41 ms
6,940 KB |
testcase_10 | AC | 35 ms
6,940 KB |
testcase_11 | AC | 41 ms
6,944 KB |
testcase_12 | AC | 38 ms
6,944 KB |
testcase_13 | AC | 43 ms
6,940 KB |
testcase_14 | AC | 36 ms
6,944 KB |
testcase_15 | AC | 38 ms
6,940 KB |
testcase_16 | AC | 38 ms
6,944 KB |
testcase_17 | AC | 37 ms
6,940 KB |
testcase_18 | AC | 55 ms
7,728 KB |
testcase_19 | AC | 38 ms
6,940 KB |
testcase_20 | AC | 43 ms
6,940 KB |
testcase_21 | AC | 32 ms
6,944 KB |
testcase_22 | AC | 12 ms
8,192 KB |
testcase_23 | AC | 12 ms
8,192 KB |
testcase_24 | AC | 13 ms
8,192 KB |
testcase_25 | AC | 56 ms
8,160 KB |
testcase_26 | AC | 57 ms
8,156 KB |
testcase_27 | AC | 56 ms
8,152 KB |
testcase_28 | AC | 57 ms
8,156 KB |
testcase_29 | AC | 57 ms
8,152 KB |
testcase_30 | AC | 57 ms
8,156 KB |
testcase_31 | AC | 50 ms
8,284 KB |
testcase_32 | AC | 49 ms
8,284 KB |
testcase_33 | AC | 49 ms
8,152 KB |
testcase_34 | AC | 48 ms
8,284 KB |
testcase_35 | AC | 49 ms
8,196 KB |
testcase_36 | AC | 49 ms
8,284 KB |
testcase_37 | AC | 12 ms
8,192 KB |
testcase_38 | AC | 48 ms
7,228 KB |
testcase_39 | AC | 40 ms
6,940 KB |
testcase_40 | AC | 12 ms
8,192 KB |
ソースコード
#![allow(unused_imports, unused_macros)] use kyoproio::*; use std::{ collections::*, io::{self, prelude::*}, iter, mem::{replace, swap}, }; fn run<I: Input, O: Write>(mut kin: I, mut out: O) { macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+).unwrap(); }; } macro_rules! outputln { ($($args:expr),+) => { output!($($args),+); outputln!(); }; () => { output!("\n"); if cfg!(debug_assertions) { out.flush().unwrap(); } } } let n: usize = kin.input(); let a: Vec<i32> = kin.seq(n); let b: Vec<i32> = kin.seq(n); if a.first() != b.first() || a.last() != b.last() { outputln!("-1"); return; } let mut xa = vec![(0, 0); n - 1]; let mut xb = vec![(0, 0); n - 1]; for i in 0..n - 1 { xa[i] = (a[i] ^ a[i + 1], i); xb[i] = (b[i] ^ b[i + 1], i); } xa.sort(); xb.sort(); let mut ij = vec![(0, 0); n - 1]; for i in 0..n - 1 { let (av, ai) = xa[i]; let (bv, bi) = xb[i]; if av != bv { outputln!("-1"); return; } ij[i] = (ai, bi); } ij.sort(); let mut fen = FenwickTree::new(n - 1, || 0, |a, b| a + b); let mut ans = 0; for (i, j) in ij { ans += i - fen.fold(j); fen.apply(j, 1); } outputln!("{}", ans); } pub struct FenwickTree<T, F, Z> { a: Vec<T>, f: F, z: Z, } impl<T, F: Fn(&T, &T) -> T, Z: Fn() -> T> FenwickTree<T, F, Z> { pub fn new(n: usize, z: Z, f: F) -> Self { Self { a: std::iter::repeat_with(&z).take(n + 1).collect(), f, z, } } pub fn apply(&mut self, mut i: usize, x: T) { i += 1; while i < self.a.len() { self.a[i] = (self.f)(&self.a[i], &x); i += i & (!i + 1); } } // [0, i) pub fn fold(&self, mut i: usize) -> T { let mut s = (self.z)(); while i > 0 { s = (self.f)(&self.a[i], &s); i -= i & (!i + 1); } s } } // ----------------------------------------------------------------------------- fn main() -> io::Result<()> { std::thread::Builder::new() .stack_size(64 * 1024 * 1024) .spawn(|| { run( KInput::new(io::stdin().lock()), io::BufWriter::new(io::stdout().lock()), ) })? .join() .unwrap(); Ok(()) } // ----------------------------------------------------------------------------- pub mod kyoproio { use std::io::prelude::*; pub trait Input { fn bytes(&mut self) -> &[u8]; fn str(&mut self) -> &str { std::str::from_utf8(self.bytes()).unwrap() } fn input<T: InputParse>(&mut self) -> T { T::input(self) } fn iter<T: InputParse>(&mut self) -> Iter<T, Self> { Iter(self, std::marker::PhantomData) } fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B { self.iter().take(n).collect() } } pub struct KInput<R> { src: R, buf: Vec<u8>, pos: usize, len: usize, } impl<R: Read> KInput<R> { pub fn new(src: R) -> Self { Self { src, buf: vec![0; 1 << 16], pos: 0, len: 0, } } } impl<R: Read> Input for KInput<R> { fn bytes(&mut self) -> &[u8] { loop { while let Some(delim) = self.buf[self.pos..self.len] .iter() .position(|b| b.is_ascii_whitespace()) { let range = self.pos..self.pos + delim; self.pos += delim + 1; if delim > 0 { return &self.buf[range]; } } if self.pos > 0 { self.buf.copy_within(self.pos..self.len, 0); self.len -= self.pos; self.pos = 0; } if self.len >= self.buf.len() { self.buf.resize(2 * self.buf.len(), 0); } let read = self.src.read(&mut self.buf[self.len..]).unwrap(); if read == 0 { let range = self.pos..self.len; self.pos = self.len; return &self.buf[range]; } self.len += read; } } } pub struct Iter<'a, T, I: ?Sized>(&'a mut I, std::marker::PhantomData<*const T>); impl<'a, T: InputParse, I: Input + ?Sized> Iterator for Iter<'a, T, I> { type Item = T; fn next(&mut self) -> Option<T> { Some(self.0.input()) } } pub trait InputParse: Sized { fn input<I: Input + ?Sized>(src: &mut I) -> Self; } impl InputParse for Vec<u8> { fn input<I: Input + ?Sized>(src: &mut I) -> Self { src.bytes().to_owned() } } macro_rules! from_str_impl { { $($T:ty)* } => { $(impl InputParse for $T { fn input<I: Input + ?Sized>(src: &mut I) -> Self { src.str().parse::<$T>().unwrap() } })* } } from_str_impl! { String char bool f32 f64 } macro_rules! parse_int_impl { { $($I:ty: $U:ty)* } => { $(impl InputParse for $I { fn input<I: Input + ?Sized>(src: &mut I) -> Self { let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $I); let s = src.bytes(); if let Some((&b'-', t)) = s.split_first() { -f(t) } else { f(s) } } } impl InputParse for $U { fn input<I: Input + ?Sized>(src: &mut I) -> Self { src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $U) } })* }; } parse_int_impl! { isize:usize i8:u8 i16:u16 i32:u32 i64:u64 i128:u128 } macro_rules! tuple_impl { ($H:ident $($T:ident)*) => { impl<$H: InputParse, $($T: InputParse),*> InputParse for ($H, $($T),*) { fn input<I: Input + ?Sized>(src: &mut I) -> Self { ($H::input(src), $($T::input(src)),*) } } tuple_impl!($($T)*); }; () => {} } tuple_impl!(A B C D E F G); macro_rules! array_impl { { $($N:literal)* } => { $(impl<T: InputParse> InputParse for [T; $N] { fn input<I: Input + ?Sized>(src: &mut I) -> Self { let mut arr = std::mem::MaybeUninit::uninit(); unsafe { let ptr = arr.as_mut_ptr() as *mut T; for i in 0..$N { ptr.add(i).write(src.input()); } arr.assume_init() } } })* }; } array_impl! { 1 2 3 4 5 6 7 8 } #[macro_export] macro_rules! kdbg { ($($v:expr),*) => { if cfg!(debug_assertions) { dbg!($($v),*) } else { ($($v),*) } } } }