結果

問題 No.670 log は定数
ユーザー tanzaku
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 where
T: 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>() }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0