結果
問題 | No.2308 [Cherry 5th Tune B] もしかして、真? |
ユーザー | haihamabossu |
提出日時 | 2023-05-19 22:45:57 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 264 ms / 2,000 ms |
コード長 | 5,655 bytes |
コンパイル時間 | 12,597 ms |
コンパイル使用メモリ | 406,176 KB |
実行使用メモリ | 25,732 KB |
最終ジャッジ日時 | 2024-12-20 01:19:38 |
合計ジャッジ時間 | 23,393 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 195 ms
8,124 KB |
testcase_02 | AC | 228 ms
14,848 KB |
testcase_03 | AC | 210 ms
12,328 KB |
testcase_04 | AC | 211 ms
13,932 KB |
testcase_05 | AC | 215 ms
13,932 KB |
testcase_06 | AC | 237 ms
20,676 KB |
testcase_07 | AC | 231 ms
19,772 KB |
testcase_08 | AC | 239 ms
21,496 KB |
testcase_09 | AC | 238 ms
21,824 KB |
testcase_10 | AC | 218 ms
13,084 KB |
testcase_11 | AC | 229 ms
14,404 KB |
testcase_12 | AC | 227 ms
13,104 KB |
testcase_13 | AC | 225 ms
13,040 KB |
testcase_14 | AC | 226 ms
12,912 KB |
testcase_15 | AC | 229 ms
12,916 KB |
testcase_16 | AC | 226 ms
14,892 KB |
testcase_17 | AC | 232 ms
14,692 KB |
testcase_18 | AC | 227 ms
15,344 KB |
testcase_19 | AC | 228 ms
15,176 KB |
testcase_20 | AC | 227 ms
14,660 KB |
testcase_21 | AC | 254 ms
24,280 KB |
testcase_22 | AC | 257 ms
23,960 KB |
testcase_23 | AC | 263 ms
24,012 KB |
testcase_24 | AC | 261 ms
23,576 KB |
testcase_25 | AC | 258 ms
24,600 KB |
testcase_26 | AC | 260 ms
23,476 KB |
testcase_27 | AC | 261 ms
23,476 KB |
testcase_28 | AC | 264 ms
25,156 KB |
testcase_29 | AC | 256 ms
25,732 KB |
testcase_30 | AC | 258 ms
23,532 KB |
testcase_31 | AC | 201 ms
23,048 KB |
testcase_32 | AC | 199 ms
23,504 KB |
testcase_33 | AC | 199 ms
24,540 KB |
testcase_34 | AC | 203 ms
23,668 KB |
testcase_35 | AC | 202 ms
24,368 KB |
testcase_36 | AC | 198 ms
24,776 KB |
testcase_37 | AC | 18 ms
6,820 KB |
testcase_38 | AC | 229 ms
13,096 KB |
ソースコード
//https://github.com/rust-lang-ja/ac-library-rs pub mod fenwicktree { use std::ops::{Bound, RangeBounds}; // Reference: https://en.wikipedia.org/wiki/Fenwick_tree pub struct FenwickTree<T> { n: usize, ary: Vec<T>, e: T, } impl<T: Clone + std::ops::AddAssign<T>> FenwickTree<T> { pub fn new(n: usize, e: T) -> Self { FenwickTree { n, ary: vec![e.clone(); n], e, } } pub fn accum(&self, mut idx: usize) -> T { let mut sum = self.e.clone(); while idx > 0 { sum += self.ary[idx - 1].clone(); idx &= idx - 1; } sum } /// performs data[idx] += val; pub fn add<U: Clone>(&mut self, mut idx: usize, val: U) where T: std::ops::AddAssign<U>, { let n = self.n; idx += 1; while idx <= n { self.ary[idx - 1] += val.clone(); idx += idx & idx.wrapping_neg(); } } /// Returns data[l] + ... + data[r - 1]. pub fn sum<R>(&self, range: R) -> T where T: std::ops::Sub<Output = T>, R: RangeBounds<usize>, { let r = match range.end_bound() { Bound::Included(r) => r + 1, Bound::Excluded(r) => *r, Bound::Unbounded => self.n, }; let l = match range.start_bound() { Bound::Included(l) => *l, Bound::Excluded(l) => l + 1, Bound::Unbounded => return self.accum(r), }; self.accum(r) - self.accum(l) } } #[cfg(test)] mod tests { use super::*; use std::ops::Bound::*; #[test] fn fenwick_tree_works() { let mut bit = FenwickTree::new(5, 0i64); // [1, 2, 3, 4, 5] for i in 0..5 { bit.add(i, i as i64 + 1); } assert_eq!(bit.sum(0..5), 15); assert_eq!(bit.sum(0..4), 10); assert_eq!(bit.sum(1..3), 5); assert_eq!(bit.sum(..), 15); assert_eq!(bit.sum(..2), 3); assert_eq!(bit.sum(..=2), 6); assert_eq!(bit.sum(1..), 14); assert_eq!(bit.sum(1..=3), 9); assert_eq!(bit.sum((Excluded(0), Included(2))), 5); } } } use fenwicktree::*; pub mod scanner { pub struct Scanner { buf: Vec<String>, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next<T: std::str::FromStr>(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec<String> { source .split_whitespace() .rev() .map(String::from) .collect::<Vec<_>>() } } } use std::ops::Deref; use crate::scanner::Scanner; use crate::FenwickTree; fn main() { let mut scanner = Scanner::new(); let t: usize = scanner.next(); for _ in 0..t { solve(&mut scanner); } } fn solve(scanner: &mut Scanner) { let n: usize = scanner.next(); let mut x: Vec<bool> = (0..n) .map(|_| { let s = scanner.next::<String>(); s.deref() == "True" }) .collect(); let y: Vec<usize> = (0..n - 1) .map(|_| { let s = scanner.next::<String>(); match s.deref() { "and" => 0, "or" => 1, "xor" => 2, _ => 3, } }) .collect(); let s: Vec<usize> = (0..n - 1).map(|_| scanner.next::<usize>()).collect(); let mut bit = FenwickTree::new(n, 0i64); for i in 0..n { bit.add(i, 1); } let cont = |ok: usize, ng: usize| -> bool { let l = ok.min(ng); let r = ok.max(ng); l + 1 < r }; for &si in s.iter() { let si = si as i64; let i: usize; { let mut ok: usize = 0; let mut ng: usize = n + 1; while cont(ok, ng) { let x = (ok + ng) / 2; if bit.sum(0..x) < si { ok = x; } else { ng = x; } } i = ok; } let j: usize; { let mut ok: usize = 0; let mut ng: usize = n + 1; while cont(ok, ng) { let x = (ok + ng) / 2; if bit.sum(0..x) < si + 1 { ok = x; } else { ng = x; } } j = ok; } bit.add(i, -1); match y[i] { 0 => x[j] = x[i] && x[j], 1 => x[j] = x[i] || x[j], 2 => x[j] = x[i] ^ x[j], _ => { if !x[i] { x[j] = true } } } } if x[n - 1] { println!("True"); } else { println!("False"); } }