結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 sakikuroe
|
| 提出日時 | 2022-08-13 10:24:40 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 8,166 bytes |
| コンパイル時間 | 13,896 ms |
| コンパイル使用メモリ | 408,208 KB |
| 実行使用メモリ | 11,264 KB |
| 最終ジャッジ日時 | 2024-09-24 14:19:03 |
| 合計ジャッジ時間 | 19,262 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | AC | 267 ms
6,940 KB |
| testcase_04 | RE | - |
| testcase_05 | AC | 55 ms
11,264 KB |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | AC | 1 ms
6,940 KB |
| testcase_35 | AC | 0 ms
6,940 KB |
コンパイルメッセージ
warning: variable does not need to be mutable
--> src/main.rs:81:17
|
81 | let mut p = self.parent;
| ----^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:82:17
|
82 | let mut pp = (*p).parent;
| ----^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:83:17
|
83 | let mut c;
| ----^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:172:25
|
172 | fn merge(&mut self, mut r_root: *mut SplayNode) -> *mut SplayNode {
| ----^^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:199:13
|
199 | let mut l_root = (*root).left;
| ----^^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:200:13
|
200 | let mut r_root = root;
| ----^^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:211:13
|
211 | let mut l_root = (*root).left;
| ----^^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:212:13
|
212 | let mut r_root = (*root).right;
| ----^^^^^^
| |
| help: remove this `mut`
ソースコード
use std::{
cmp::Ordering,
ptr::{self, null_mut},
};
macro_rules! read_line {
($($xs: tt)*) => {
let mut buf = String::new();
std::io::stdin().read_line(&mut buf).unwrap();
let mut iter = buf.split_whitespace();
expand!(iter, $($xs)*);
};
}
macro_rules! expand {
($iter: expr,) => {};
($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => {
let mut $var = value!($iter, $type);
expand!($iter, $($xs)*);
};
($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => {
let $var = value!($iter, $type);
expand!($iter, $($xs)*);
};
}
macro_rules! value {
($iter:expr, ($($type: tt),*)) => {
($(value!($iter, $type)),*);
};
($iter: expr, [$type: tt; $len: expr]) => {
(0..$len).map(|_| value!($iter, $type)).collect::<Vec<_>>()
};
($iter: expr, Chars) => {
value!($iter, String).chars().collect::<Vec<_>>>()
};
($iter: expr, $type: ty) => {
if let Some(v) = $iter.next() {
v.parse::<$type>().ok()
} else {
None
}
};
}
#[derive(Clone, PartialEq, Eq)]
struct SplayNode {
key: isize,
left: *mut Self,
right: *mut Self,
parent: *mut Self,
size: usize,
}
impl SplayNode {
fn new(key: isize) -> Self {
SplayNode {
key,
left: null_mut(),
right: null_mut(),
parent: null_mut(),
size: 1,
}
}
fn update(&mut self) {
unsafe {
self.size = 1;
if !self.left.is_null() {
self.size += (*(self.left)).size;
}
if !self.right.is_null() {
self.size += (*(self.right)).size;
}
}
}
fn rotate(&mut self) {
unsafe {
let mut p = self.parent;
let mut pp = (*p).parent;
let mut c;
if (*p).left == self {
c = self.right;
self.right = p;
(*p).left = c;
} else {
c = self.left;
self.left = p;
(*p).right = c;
}
if !pp.is_null() {
if (*pp).left == p {
(*pp).left = self;
}
if (*pp).right == p {
(*pp).right = self;
}
}
self.parent = pp;
(*p).parent = self;
if !c.is_null() {
(*c).parent = p;
}
(*p).update();
self.update();
}
}
fn state(&self) -> isize {
unsafe {
if !self.parent.is_null() && ptr::eq((*self.parent).left, self) {
1
} else if !self.parent.is_null() && ptr::eq((*self.parent).right, self) {
-1
} else {
0
}
}
}
fn splay(&mut self) {
unsafe {
while !self.parent.is_null() {
if (*self.parent).state() == 0 {
// zig
self.rotate();
} else if (*self).state() == (*self.parent).state() {
// zig-zag
(*self.parent).rotate();
(*self).rotate();
} else {
// zig-zig
(*self).rotate();
(*self).rotate();
}
}
}
}
fn get(&mut self, mut idx: usize) -> *mut SplayNode {
let mut root = self as *mut SplayNode;
unsafe {
loop {
let lsize = if !(*root).left.is_null() {
(*(*root).left).size
} else {
0
};
match idx.cmp(&lsize) {
Ordering::Less => {
root = (*root).left;
}
Ordering::Equal => {
(*root).splay();
return root;
}
Ordering::Greater => {
root = (*root).right;
idx = idx - lsize - 1;
}
}
}
}
}
fn merge(&mut self, mut r_root: *mut SplayNode) -> *mut SplayNode {
let mut l_root = self as *mut SplayNode;
unsafe {
if l_root.is_null() {
r_root
} else if r_root.is_null() {
l_root
} else {
l_root = (*l_root).get((*l_root).size - 1);
(*l_root).right = r_root;
(*r_root).parent = l_root;
(*l_root).update();
l_root
}
}
}
}
fn split(mut root: *mut SplayNode, idx: usize) -> (*mut SplayNode, *mut SplayNode) {
unsafe {
if idx == 0 {
return (null_mut(), root);
}
if idx == (*root).size {
return (root, null_mut());
}
root = (*root).get(idx);
let mut l_root = (*root).left;
let mut r_root = root;
(*r_root).left = null_mut();
(*l_root).parent = null_mut();
(*r_root).update();
(l_root, r_root)
}
}
fn remove(mut root: *mut SplayNode, idx: usize) -> (*mut SplayNode, *mut SplayNode) {
unsafe {
root = (*root).get(idx);
let mut l_root = (*root).left;
let mut r_root = (*root).right;
if !l_root.is_null() {
(*l_root).parent = null_mut()
};
if !r_root.is_null() {
(*r_root).parent = null_mut()
};
(*root).left = null_mut();
(*root).right = null_mut();
(*root).update();
((*l_root).merge(r_root), root)
}
}
fn lower_bound(root: *mut SplayNode, x: isize) -> usize {
unsafe {
if x <= (*root).key {
if (*root).left.is_null() {
return 0;
} else {
lower_bound((*root).left, x)
}
} else {
(if (*root).left.is_null() {
0
} else {
(*(*root).left).size
}) + if (*root).right.is_null() {
0
} else {
lower_bound((*root).right, x)
} + 1
}
}
}
fn insert(root: *mut SplayNode, node: *mut SplayNode) -> *mut SplayNode {
let idx = unsafe { lower_bound(root, (*node).key) };
let (l_root, r_root) = split(root, idx);
unsafe { (*((*l_root).merge(node))).merge(r_root) }
}
pub struct SplayBST {
root: *mut SplayNode,
}
impl SplayBST {
fn new() -> Self {
SplayBST { root: null_mut() }
}
fn insert(&mut self, x: isize) {
let add = Box::into_raw(Box::new(SplayNode::new(x)));
if (self.root as *mut SplayNode).is_null() {
self.root = add;
} else {
self.root = insert((*self).root, add);
}
}
fn get(&mut self, idx: usize) -> Option<isize> {
unsafe {
if (*self).root.is_null() {
return None;
}
if (*(*self).root).size <= idx {
return None;
}
self.root = (*self.root).get(idx);
if self.root.is_null() {
None
} else {
Some((*self.root).key)
}
}
}
fn remove(&mut self, x: isize) {
let idx = lower_bound((*self).root, x);
self.root = remove((*self).root, idx).0;
}
}
fn main() {
read_line! {
q: usize, k: usize,
}
let (q, k) = (q.unwrap(), k.unwrap());
let mut bst = SplayBST::new();
for _ in 0..q {
read_line! {
t: usize, v: isize,
}
let t = t.unwrap();
if t == 1 {
let v = v.unwrap();
bst.insert(v);
} else {
if let Some(v) = bst.get(k - 1) {
println!("{}", v);
bst.remove(v);
} else {
println!("-1");
}
}
}
}