fn solve(s: Vec, t: Vec) -> i64 { let n = s.len(); if s[0] != t[0] || s[n - 1] != t[n - 1] { return -1; } let mut s = s .windows(2) .map(|s| (s[0] == s[1]) as usize) .collect::>(); let mut t = t .windows(2) .map(|s| (s[0] == s[1]) as usize) .collect::>(); for (i, s) in s.iter_mut().enumerate() { *s ^= i & 1; } for (i, s) in t.iter_mut().enumerate() { *s ^= i & 1; } let mut x = vec![vec![]; 2]; for (i, t) in t.iter().enumerate().rev() { x[*t].push(i); } let mut bit = Fenwick::new(n, 0i64); let mut ans = 0; for (i, s) in s.iter().enumerate() { if let Some(x) = x[*s].pop() { ans += i as i64 - bit.sum(x + 1); bit.add(x + 1, 1); } else { return -1; } } ans } fn run() { input! { n: usize, s: bytes, t: bytes, } println!("{}", solve(s, t)); } fn main() { run(); } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // 1-indexedなBIT // 座標xへの加算、[1,x]の和, ([1,x]の和)>=s となる最小のxの探索 // ---------- begin fenwick tree ---------- pub struct Fenwick { zero: T, a: Box<[T]>, } impl Fenwick where T: Copy + std::ops::Add, { pub fn new(size: usize, zero: T) -> Fenwick { Fenwick { zero: zero, a: vec![zero; size + 1].into_boxed_slice(), } } pub fn init(&mut self) { for a in self.a.iter_mut() { *a = self.zero; } } pub fn add(&mut self, mut x: usize, v: T) { assert!(x > 0); while let Some(a) = self.a.get_mut(x) { *a = *a + v; x += x & (!x + 1); } } pub fn sum(&self, mut x: usize) -> T { assert!(x < self.a.len()); let mut res = self.zero; while x > 0 { res = res + self.a[x]; x -= x & (!x + 1); } res } } impl Fenwick where T: Copy + std::ops::Add + PartialOrd, { pub fn search(&self, s: T) -> usize { debug_assert!(self.sum(self.a.len() - 1) >= s); let mut k = 1; while 2 * k < self.a.len() { k *= 2; } let mut x = 0; let mut w = self.zero; while k > 0 { self.a.get(x + k).map(|a| { if w + *a < s { w = w + *a; x += k; } }); k >>= 1; } x + 1 } } // ---------- end fenwick tree ----------