結果
問題 | No.670 log は定数 |
ユーザー |
|
提出日時 | 2018-03-24 01:09:47 |
言語 | Rust (1.83.0 + proconio) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,912 bytes |
コンパイル時間 | 13,911 ms |
コンパイル使用メモリ | 387,860 KB |
実行使用メモリ | 800,540 KB |
最終ジャッジ日時 | 2024-06-25 02:33:38 |
合計ジャッジ時間 | 24,505 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | MLE * 1 -- * 9 |
ソースコード
struct Rand {seed: u64,}impl Rand {fn new(seed: u64) -> Self {Rand { seed: seed, }}fn next(&mut self) -> u64 {self.seed = self.seed ^ (self.seed << 13);self.seed = self.seed ^ (self.seed >> 7);self.seed = self.seed ^ (self.seed << 17);self.seed >> 33}}fn radix_sort(xs: &mut Vec<u64>) {let mut ys = xs.clone();for i in 0..4 {let i = i*16;let mut cnt = [0; (1<<16)+1];xs.iter().for_each(|x| {let key = (x >> i & 0xFFFF_u64) as usize;cnt[key+1] += 1;});for j in 1..cnt.len() {cnt[j] += cnt[j-1];}xs.iter().for_each(|x| {let key = (x >> i & 0xFFFF_u64) as usize;ys[cnt[key]] = *x;cnt[key] += 1;});std::mem::swap(xs, &mut ys);}}fn main() {let mut cin = Scanner::new();let n = cin.next();let q = cin.next();let seed = cin.next();let mut rand = Rand::new(seed);let mut xs = Vec::with_capacity((n + q) as usize);(0..10000).for_each(|_| { rand.next(); });(0..n).for_each(|_| xs.push(rand.next()<<32|(q as u64)));(0..q).for_each(|i| xs.push(rand.next()<<32|(i as u64)));radix_sort(&mut xs);let mut ans = 0;let mut cnt = 0;xs.into_iter().for_each(|x| {let idx = x & 0xFFFF_FFFF;if idx == q {cnt += 1;} else {ans ^= idx * cnt;}});println!("{}", ans);}struct Scanner {reader: std::io::Stdin,tokens: std::collections::VecDeque<String>,}impl Scanner {fn new() -> Self {Scanner {reader: std::io::stdin(),tokens: std::collections::VecDeque::new(),}}fn next_string(&mut self) -> String {if self.tokens.is_empty() {let mut s = String::new();loop {self.reader.read_line(&mut s).ok();let s = s.trim();if s.len() != 0 {for it in s.split_whitespace() {self.tokens.push_back(it.into())}break;}}}self.tokens.pop_front().unwrap()}fn next<T>(&mut self) -> T whereT: std::str::FromStr + std::marker::Copy,<T as std::str::FromStr>::Err: std::fmt::Debug{self.next_string().parse().unwrap()}#[allow(dead_code)] fn next_i32(&mut self) -> i32 { self.next::<i32>() }#[allow(dead_code)] fn next_i64(&mut self) -> i64 { self.next::<i64>() }#[allow(dead_code)] fn next_u64(&mut self) -> u64 { self.next::<u64>() }#[allow(dead_code)] fn next_usize(&mut self) -> usize { self.next::<usize>() }#[allow(dead_code)] fn next_isize(&mut self) -> isize { self.next::<isize>() }}