結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー |
|
提出日時 | 2023-05-22 15:20:55 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 7,483 bytes |
コンパイル時間 | 14,520 ms |
コンパイル使用メモリ | 398,852 KB |
実行使用メモリ | 28,800 KB |
最終ジャッジ日時 | 2024-12-22 11:14:57 |
合計ジャッジ時間 | 27,377 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
#![allow(non_snake_case)]#![allow(unused_imports)]#![allow(unused_macros)]#![allow(clippy::needless_range_loop)]#![allow(clippy::comparison_chain)]#![allow(clippy::nonminimal_bool)]#![allow(clippy::neg_multiply)]#![allow(dead_code)]// use itertools::Itertools;// use superslice::Ext;use std::cmp::Reverse;use std::collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque};#[derive(Default)]struct Solver {}impl Solver {fn solve(&mut self) {input! {T: usize,}let f = |a: bool, b: bool, e: &String| -> bool {if e.as_str() == "and" {a & b} else if e.as_str() == "or" {a | b} else if e.as_str() == "xor" {a ^ b} else {!a | b}};for _ in 0..T {input! {N: usize,X: [String; N],Y: [String; N - 1],S: [usize; N - 1]}let mut X: Vec<bool> = X.iter().map(|x| x.as_str() == "True").collect();let mut bset_u = BinaryIndexedTree::new(N);bset_u.build(vec![1; N]);let mut bset_v = BinaryIndexedTree::new(N - 1);bset_v.build(vec![1; N - 1]);let mut ans = true;for &s in &S {let pos_u0 = bset_u.lower_bound(s as isize) as usize;let pos_u1 = bset_u.lower_bound(s as isize + 1) as usize;let pos_v = bset_v.lower_bound(s as isize) as usize;ans = f(X[pos_u0], X[pos_u1], &Y[pos_v]);X[pos_u0] = ans;bset_u.add(pos_u1, -1);bset_v.add(pos_v, -1);}if ans {println!("True");} else {println!("False");}}}}#[derive(Debug, Clone)]struct BinaryIndexedTree {size: usize,data: Vec<isize>,}impl BinaryIndexedTree {fn new(n: usize) -> Self {BinaryIndexedTree {size: n,data: vec![0; n],}}fn build(&mut self, v: Vec<isize>) {assert_eq!(self.size, v.len(), "size not correct!");self.data = v;for i in 1..=self.size {let idx = (i as isize & -(i as isize)) as usize;if i + idx <= self.size {self.data[i + idx - 1] += self.data[i - 1];}}}fn add(&mut self, i: usize, x: isize) {let mut idx = i + 1;while idx <= self.size {self.data[idx - 1] += x;idx += (idx as isize & -(idx as isize)) as usize;}}// [0, r)fn sum(&self, i: usize) -> isize {let mut ret = 0;let mut idx = i;while idx > 0 {ret += self.data[idx - 1];idx -= (idx as isize & -(idx as isize)) as usize;}ret}// [l, r)fn range_sum(&self, l: usize, r: usize) -> isize {self.sum(r) - self.sum(l)}fn lower_bound(&self, x: isize) -> isize {let mut i = 0;let mut k = 1;let mut x = x;while k <= self.size {k <<= 1;}while k > 0 {if i + k <= self.size && self.data[i + k - 1] < x {x -= self.data[i + k - 1];i += k;}k >>= 1;}if x > 0 {i as isize} else {-1}}fn upper_bound(&self, x: isize) -> isize {let mut i = 0;let mut k = 1;let mut x = x;while k <= self.size {k <<= 1;}while k > 0 {if i + k <= self.size && self.data[i + k - 1] <= x {x -= self.data[i + k - 1];i += k;}k >>= 1;}if i < self.size {i as isize} else {-1}}}#[macro_export]macro_rules! max {($x: expr) => ($x);($x: expr, $( $y: expr ),+) => {std::cmp::max($x, max!($( $y ),+))}}#[macro_export]macro_rules! min {($x: expr) => ($x);($x: expr, $( $y: expr ),+) => {std::cmp::min($x, min!($( $y ),+))}}fn main() {std::thread::Builder::new().stack_size(128 * 1024 * 1024).spawn(|| Solver::default().solve()).unwrap().join().unwrap();}#[macro_export]macro_rules! input {() => {};(mut $var:ident: $t:tt, $($rest:tt)*) => {let mut $var = __input_inner!($t);input!($($rest)*)};($var:ident: $t:tt, $($rest:tt)*) => {let $var = __input_inner!($t);input!($($rest)*)};(mut $var:ident: $t:tt) => {let mut $var = __input_inner!($t);};($var:ident: $t:tt) => {let $var = __input_inner!($t);};}#[macro_export]macro_rules! __input_inner {(($($t:tt),*)) => {($(__input_inner!($t)),*)};([$t:tt; $n:expr]) => {(0..$n).map(|_| __input_inner!($t)).collect::<Vec<_>>()};([$t:tt]) => {{let n = __input_inner!(usize);(0..n).map(|_| __input_inner!($t)).collect::<Vec<_>>()}};(chars) => {__input_inner!(String).chars().collect::<Vec<_>>()};(bytes) => {__input_inner!(String).into_bytes()};(usize1) => {__input_inner!(usize) - 1};($t:ty) => {$crate::read::<$t>()};}#[macro_export]macro_rules! println {() => {$crate::write(|w| {use std::io::Write;std::writeln!(w).unwrap()})};($($arg:tt)*) => {$crate::write(|w| {use std::io::Write;std::writeln!(w, $($arg)*).unwrap()})};}#[macro_export]macro_rules! print {($($arg:tt)*) => {$crate::write(|w| {use std::io::Write;std::write!(w, $($arg)*).unwrap()})};}#[macro_export]macro_rules! flush {() => {$crate::write(|w| {use std::io::Write;w.flush().unwrap()})};}pub fn read<T>() -> TwhereT: std::str::FromStr,T::Err: std::fmt::Debug,{use std::cell::RefCell;use std::io::*;thread_local! {pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());}STDIN.with(|r| {let mut r = r.borrow_mut();let mut s = vec![];loop {let buf = r.fill_buf().unwrap();if buf.is_empty() {break;}if let Some(i) = buf.iter().position(u8::is_ascii_whitespace) {s.extend_from_slice(&buf[..i]);r.consume(i + 1);if !s.is_empty() {break;}} else {s.extend_from_slice(buf);let n = buf.len();r.consume(n);}}std::str::from_utf8(&s).unwrap().parse().unwrap()})}pub fn write<F>(f: F)whereF: FnOnce(&mut std::io::BufWriter<std::io::StdoutLock>),{use std::cell::RefCell;use std::io::*;thread_local! {pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> =RefCell::new(BufWriter::new(stdout().lock()));}STDOUT.with(|w| f(&mut w.borrow_mut()))}