結果
| 問題 | No.930 数列圧縮 |
| ユーザー |
 akiradeveloper
|
| 提出日時 | 2019-11-22 22:16:14 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 252 ms / 2,000 ms |
| コード長 | 12,316 bytes |
| コンパイル時間 | 14,460 ms |
| コンパイル使用メモリ | 382,024 KB |
| 実行使用メモリ | 11,776 KB |
| 最終ジャッジ日時 | 2024-10-11 03:57:42 |
| 合計ジャッジ時間 | 18,619 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 1 ms
5,248 KB |
| testcase_03 | AC | 1 ms
5,248 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | AC | 3 ms
5,248 KB |
| testcase_06 | AC | 2 ms
5,248 KB |
| testcase_07 | AC | 4 ms
5,248 KB |
| testcase_08 | AC | 108 ms
8,576 KB |
| testcase_09 | AC | 109 ms
9,728 KB |
| testcase_10 | AC | 92 ms
7,040 KB |
| testcase_11 | AC | 115 ms
8,832 KB |
| testcase_12 | AC | 146 ms
9,984 KB |
| testcase_13 | AC | 70 ms
5,888 KB |
| testcase_14 | AC | 99 ms
6,400 KB |
| testcase_15 | AC | 129 ms
11,776 KB |
| testcase_16 | AC | 189 ms
11,264 KB |
| testcase_17 | AC | 175 ms
11,392 KB |
| testcase_18 | AC | 137 ms
11,392 KB |
| testcase_19 | AC | 187 ms
11,392 KB |
| testcase_20 | AC | 201 ms
11,520 KB |
| testcase_21 | AC | 226 ms
11,520 KB |
| testcase_22 | AC | 1 ms
5,248 KB |
| testcase_23 | AC | 252 ms
11,392 KB |
| testcase_24 | AC | 1 ms
5,248 KB |
| testcase_25 | AC | 1 ms
5,248 KB |
| testcase_26 | AC | 1 ms
5,248 KB |
コンパイルメッセージ
warning: unused variable: `t2`
--> src/main.rs:289:14
|
289 | let (t2, t3) = split(rest, 1);
| ^^ help: if this is intentional, prefix it with an underscore: `_t2`
|
= note: `#[warn(unused_variables)]` on by default
warning: methods `lower_bound`, `orderd_insert`, `split`, and `len` are never used
--> src/main.rs:317:12
|
309 | impl Treap {
| ---------- methods in this implementation
...
317 | pub fn lower_bound(&mut self, l: usize, r: usize, v: i64) -> usize {
| ^^^^^^^^^^^
...
325 | pub fn orderd_insert(&mut self, v: i64) {
| ^^^^^^^^^^^^^
...
349 | pub fn split(self, k: usize) -> (Treap, Treap) {
| ^^^^^
...
362 | pub fn len(&self) -> usize {
| ^^^
|
= note: `#[warn(dead_code)]` on by default
warning: function `bisect` is never used
--> src/main.rs:292:12
|
292 | pub fn bisect(t: &Option<Box<Node>>, v: i64) -> usize {
| ^^^^^^
warning: variable `N` should have a snake case name
--> src/main.rs:112:9
|
112 | N:usize,
| ^ help: convert the identifier to snake case: `n`
|
= note: `#[warn(non_snake_case)]` on by default
ソースコード
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[macro_export]
macro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }
#[macro_export]
macro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }
#[macro_export]
macro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
#[macro_export]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }
#[macro_export]
macro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( "Parse error" ) } ; }
use std::io;
use std::io::BufRead;
use std::str;
pub struct Parser<R> {
reader: R,
buf: Vec<u8>,
pos: usize,
}
impl Parser<io::Empty> {
pub fn from_str(s: &str) -> Parser<io::Empty> {
Parser {
reader: io::empty(),
buf: s.as_bytes().to_vec(),
pos: 0,
}
}
}
impl<R: BufRead> Parser<R> {
pub fn new(reader: R) -> Parser<R> {
Parser {
reader: reader,
buf: vec![],
pos: 0,
}
}
pub fn update_buf(&mut self) {
self.buf.clear();
self.pos = 0;
loop {
let (len, complete) = {
let buf2 = self.reader.fill_buf().unwrap();
self.buf.extend_from_slice(buf2);
let len = buf2.len();
if len == 0 {
break;
}
(len, buf2[len - 1] <= 0x20)
};
self.reader.consume(len);
if complete {
break;
}
}
}
pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {
loop {
let mut begin = self.pos;
while begin < self.buf.len() && (self.buf[begin] <= 0x20) {
begin += 1;
}
let mut end = begin;
while end < self.buf.len() && (self.buf[end] > 0x20) {
end += 1;
}
if begin != self.buf.len() {
self.pos = end;
return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();
} else {
self.update_buf();
}
}
}
}
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
use std::thread;
if BIG_STACK_SIZE {
thread::Builder::new()
.stack_size(32 * 1024 * 1024)
.name("solve".into())
.spawn(solve)
.unwrap()
.join()
.unwrap();
} else {
solve();
}
}
fn solve() {
input!{
N:usize,
a:[i64;N]
}
let mut tr = Treap::new();
for i in 0..N {
tr.insert(i, a[i]);
}
let mut n = N;
let mut cur = n-1;
let mut res = vec![];
loop {
if cur == 0 {
break;
}
let i = cur-1;
let j = cur;
let x = tr.get(i);
let y = tr.get(j);
if x < y {
if j == n-1 {
tr.erase(i);
res.push(x);
n -= 1;
cur -= 1;
} else {
tr.erase(j);
res.push(y);
n -= 1;
}
} else {
cur -= 1;
}
}
if res.len() == N-1 {
println!("Yes");
let s = vec_to_string(&res).join(" ");
println!("{}", s);
} else {
println!("No");
}
}
pub fn vec_to_string<T: ToString>(xs: &[T]) -> Vec<String> {
let mut res = vec![];
for x in xs {
res.push(x.to_string());
}
res
}
#[derive(Debug, Clone)]
#[allow(dead_code)]
pub struct Xorshift {
seed: u64,
}
impl Xorshift {
#[allow(dead_code)]
pub fn new() -> Xorshift {
Xorshift {
seed: 0xf0fb588ca2196dac,
}
}
#[allow(dead_code)]
pub fn with_seed(seed: u64) -> Xorshift {
Xorshift { seed: seed }
}
#[inline(always)]
#[allow(dead_code)]
pub 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
}
#[inline(always)]
#[allow(dead_code)]
pub fn rand(&mut self, m: u64) -> u64 {
self.next() % m
}
#[inline(always)]
#[allow(dead_code)]
pub fn randf(&mut self) -> f64 {
use std::mem;
const UPPER_MASK: u64 = 0x3FF0000000000000;
const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
let tmp = UPPER_MASK | (self.next() & LOWER_MASK);
let result: f64 = unsafe { mem::transmute(tmp) };
result - 1.0
}
}
#[doc = " https://www.slideshare.net/iwiwi/2-12188757"]
mod treap {
#[derive(Clone, Debug)]
pub struct Node {
pub v: i64,
pri: u64,
lch: Option<Box<Node>>,
rch: Option<Box<Node>>,
cnt: usize,
sum: i64,
}
pub fn new_node(v: i64, rand: u64) -> Node {
Node {
v: v,
pri: rand,
lch: None.into(),
rch: None.into(),
cnt: 1,
sum: v,
}
}
pub fn count(t: &Option<Box<Node>>) -> usize {
match *t {
Some(ref x) => x.cnt,
None => 0,
}
}
pub fn sum(t: &Option<Box<Node>>) -> i64 {
match *t {
Some(ref x) => x.sum,
None => 0,
}
}
fn update(t: Box<Node>) -> Box<Node> {
let mut t = t;
t.cnt = count(&t.lch) + count(&t.rch) + 1;
t.sum = sum(&t.lch) + sum(&t.rch) + t.v;
t
}
pub fn merge(l: Option<Box<Node>>, r: Option<Box<Node>>) -> Option<Box<Node>> {
if l.is_none() && r.is_none() {
return None;
}
if l.is_none() {
return r;
}
if r.is_none() {
return l;
}
assert!(l.is_some() && r.is_some());
let mut l = l.unwrap();
let mut r = r.unwrap();
if l.pri > r.pri {
let old_rch = l.rch.take();
l.rch = merge(old_rch, Some(r).into());
update(l).into()
} else {
let old_lch = r.lch.take();
r.lch = merge(Some(l).into(), old_lch);
update(r).into()
}
}
pub fn split(t: Option<Box<Node>>, k: usize) -> (Option<Box<Node>>, Option<Box<Node>>) {
if t.is_none() {
return (None.into(), None.into());
}
let mut t = t.unwrap();
let lcnt = count(&t.lch);
if k <= lcnt {
let old_lch = t.lch.take();
let s = split(old_lch, k);
t.lch = s.1;
(s.0, Some(update(t)).into())
} else {
let old_rch = t.rch.take();
let s = split(old_rch, k - lcnt - 1);
t.rch = s.0;
(Some(update(t)).into(), s.1)
}
}
pub fn insert(t: Box<Node>, k: usize, v: i64, rand: u64) -> Option<Box<Node>> {
let (l, r) = split(Some(t).into(), k);
let newt = merge(l, Some(new_node(v, rand).into()));
let newt = merge(newt, r);
newt
}
pub fn erase(t: Box<Node>, k: usize) -> Option<Box<Node>> {
let (t1, rest) = split(Some(t).into(), k);
let (t2, t3) = split(rest, 1);
merge(t1, t3)
}
pub fn bisect(t: &Option<Box<Node>>, v: i64) -> usize {
match *t {
None => 0,
Some(ref n) => {
if v <= n.v {
bisect(&n.lch, v)
} else {
count(&n.lch) + 1 + bisect(&n.rch, v)
}
}
}
}
}
struct Treap {
rng: Xorshift,
t: Option<Box<treap::Node>>,
}
impl Treap {
pub fn new() -> Treap {
Treap {
rng: Xorshift::new(),
t: None,
}
}
#[doc = "[l,r)"]
pub fn lower_bound(&mut self, l: usize, r: usize, v: i64) -> usize {
let t = self.t.take();
let (lt, t) = treap::split(t, l);
let (t, rt) = treap::split(t, r - l);
let idx = treap::count(<) + treap::bisect(&t, v);
self.t = treap::merge(lt, treap::merge(t, rt));
idx
}
pub fn orderd_insert(&mut self, v: i64) {
if self.t.is_none() {
self.insert(0, v);
} else {
let n = self.len();
let ins_pos = self.lower_bound(0, n, v);
self.insert(ins_pos, v);
}
}
pub fn insert(&mut self, k: usize, v: i64) {
if self.t.is_none() {
self.t = Some(treap::new_node(v, self.rng.next()).into());
} else {
let t = self.t.take().unwrap();
self.t = treap::insert(t, k, v, self.rng.next());
}
}
pub fn erase(&mut self, k: usize) {
if self.t.is_some() {
let t = self.t.take().unwrap();
self.t = treap::erase(t, k).into();
}
}
#[doc = "split into [l,r)+[r,n)"]
pub fn split(self, k: usize) -> (Treap, Treap) {
let (a, b) = treap::split(self.t, k);
(
Treap {
rng: self.rng.clone(),
t: a,
},
Treap {
rng: self.rng.clone(),
t: b,
},
)
}
pub fn len(&self) -> usize {
treap::count(&self.t)
}
#[doc = "[l,r)"]
pub fn sum(&mut self, l: usize, r: usize) -> i64 {
if self.t.is_none() {
return 0;
} else {
let t = self.t.take();
let (a1, a2) = treap::split(t, l);
let (b1, b2) = treap::split(a2, r - l);
let res = treap::sum(&b1);
self.t = treap::merge(treap::merge(a1, b1), b2);
res
}
}
pub fn get(&mut self, k: usize) -> i64 {
self.sum(k, k + 1)
}
}