結果
| 問題 | No.1209 XOR Into You |
| ユーザー |
 o2c
|
| 提出日時 | 2020-09-11 19:54:41 |
| 言語 | Rust (1.77.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 3,730 bytes |
| コンパイル時間 | 2,630 ms |
| コンパイル使用メモリ | 168,956 KB |
| 実行使用メモリ | 7,048 KB |
| 最終ジャッジ日時 | 2023-08-27 05:22:28 |
| 合計ジャッジ時間 | 6,379 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | RE | - |
| testcase_03 | WA | - |
| testcase_04 | AC | 29 ms
6,972 KB |
| testcase_05 | AC | 30 ms
6,964 KB |
| testcase_06 | AC | 30 ms
6,992 KB |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | WA | - |
コンパイルメッセージ
warning: variable does not need to be mutable
--> Main.rs:10:338
|
10 | ...es !read {($($t :tt ) ,*;$n :expr ) =>{{let stdin =::std ::io ::stdin () ;let ret =::std ::io ::BufRead ::lines (stdin .lock () ) .take ($n ) .map (|line |{let line =line .unwrap () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } ) .collect ::<Vec <_ >>() ;ret } } ;($($t :tt ) ,*) =>{{let line =readln () ;let mut it =l...
| ----^^
| |
| help: remove this `mut`
...
67 | ... = read!([usize]);
| -------------- in this macro invocation
|
= note: `#[warn(unused_mut)]` on by default
= note: this warning originates in the macro `read` (in Nightly builds, run with -Z macro-backtrace for more info)
warning: variable does not need to be mutable
--> Main.rs:10:338
|
10 | ...es !read {($($t :tt ) ,*;$n :expr ) =>{{let stdin =::std ::io ::stdin () ;let ret =::std ::io ::BufRead ::lines (stdin .lock () ) .take ($n ) .map (|line |{let line =line .unwrap () ;let mut it =line .spli
ソースコード
#[allow(unused_imports)]
use std::collections::*;
pub fn readln() -> String {
let mut line = String::new();
::std::io::stdin()
.read_line(&mut line)
.unwrap_or_else(|e| panic!("{}", e));
line
}
macro_rules !read {($($t :tt ) ,*;$n :expr ) =>{{let stdin =::std ::io ::stdin () ;let ret =::std ::io ::BufRead ::lines (stdin .lock () ) .take ($n ) .map (|line |{let line =line .unwrap () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } ) .collect ::<Vec <_ >>() ;ret } } ;($($t :tt ) ,*) =>{{let line =readln () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } } ;}
macro_rules !_read {($it :ident ;[char ] ) =>{_read !($it ;String ) .chars () .collect ::<Vec <_ >>() } ;($it :ident ;[u8 ] ) =>{Vec ::from (_read !($it ;String ) .into_bytes () ) } ;($it :ident ;usize1 ) =>{$it .next () .unwrap_or_else (||panic !("input mismatch" ) ) .parse ::<usize >() .unwrap_or_else (|e |panic !("{}" ,e ) ) -1 } ;($it :ident ;[usize1 ] ) =>{$it .map (|s |s .parse ::<usize >() .unwrap_or_else (|e |panic !("{}" ,e ) ) -1 ) .collect ::<Vec <_ >>() } ;($it :ident ;[$t :ty ] ) =>{$it .map (|s |s .parse ::<$t >() .unwrap_or_else (|e |panic !("{}" ,e ) ) ) .collect ::<Vec <_ >>() } ;($it :ident ;$t :ty ) =>{$it .next () .unwrap_or_else (||panic !("input mismatch" ) ) .parse ::<$t >() .unwrap_or_else (|e |panic !("{}" ,e ) ) } ;($it :ident ;$($t :tt ) ,+) =>{($(_read !($it ;$t ) ) ,*) } ;}
struct FenwickTree<T> {
n: usize,
tree: Vec<T>,
e: T,
}
#[allow(dead_code)]
impl<T: std::ops::AddAssign + Clone> FenwickTree<T> {
fn new(n: usize, e: T) -> Self {
FenwickTree {
n,
tree: vec![e.clone(); n],
e,
}
}
/// A[i] += w
fn add<U: Clone>(&mut self, mut idx: usize, w: U)
where
T: std::ops::AddAssign<U>,
{
idx += 1;
while idx <= self.n {
self.tree[idx - 1] += w.clone();
idx += idx & idx.wrapping_neg();
}
}
/// return A[0] + ... + A[idx-1]
fn accum(&self, mut idx: usize) -> T {
let mut sum = self.e.clone();
while idx > 0 {
sum += self.tree[idx - 1].clone();
idx &= idx - 1;
}
sum
}
/// return ∑ d[i] for i in R
fn sum<R>(&self, interval: R) -> T
where
T: std::ops::Sub<Output = T>,
R: std::ops::RangeBounds<usize>,
{
let r = match interval.end_bound() {
std::ops::Bound::Excluded(&a) => a,
std::ops::Bound::Included(&a) => a + 1,
_ => self.n,
};
match interval.start_bound() {
std::ops::Bound::Included(&l) => self.accum(r) - self.accum(l),
_ => self.accum(r),
}
}
}
fn main() {
let n = read!(usize);
let a = read!([usize]);
let b = read!([usize]);
let a: Vec<_> = a.windows(2).map(|w| w[0] ^ w[1]).collect();
let b: Vec<_> = b.windows(2).map(|w| w[0] ^ w[1]).collect();
let mut c = a.clone();
let mut d = b.clone();
c.sort();
d.sort();
if a[0] != b[0] || a[n - 1] != b[n - 1] || c != d {
println!("-1");
return;
}
c.dedup();
let m = c.len();
let map = (0..m).map(|i| (c[i], i)).collect::<BTreeMap<_, _>>();
let mut q = vec![std::collections::VecDeque::<usize>::new(); m];
for (i, a) in a.iter().enumerate() {
q[*map.get(a).unwrap()].push_back(i);
}
let mut ft = FenwickTree::new(n - 1, 0i64);
for i in 0..n - 1 {
ft.add(i, 1);
}
let mut ans = 0;
for b in b.iter() {
let i = q[*map.get(b).unwrap()].pop_front().unwrap();
ans += ft.sum(..i);
ft.add(i, -1);
}
println!("{}", ans);
}