結果
問題 | No.953 席 |
ユーザー | akiradeveloper |
提出日時 | 2019-12-16 18:01:05 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,849 bytes |
コンパイル時間 | 15,891 ms |
コンパイル使用メモリ | 379,968 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2024-07-02 20:16:23 |
合計ジャッジ時間 | 18,526 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 55 ms
8,704 KB |
testcase_03 | AC | 46 ms
8,064 KB |
testcase_04 | AC | 53 ms
8,576 KB |
testcase_05 | AC | 40 ms
7,936 KB |
testcase_06 | AC | 55 ms
8,576 KB |
testcase_07 | AC | 108 ms
15,104 KB |
testcase_08 | AC | 127 ms
13,056 KB |
testcase_09 | AC | 82 ms
15,488 KB |
testcase_10 | AC | 26 ms
6,400 KB |
testcase_11 | AC | 88 ms
10,112 KB |
testcase_12 | AC | 106 ms
11,008 KB |
testcase_13 | WA | - |
testcase_14 | AC | 88 ms
10,368 KB |
testcase_15 | AC | 81 ms
10,368 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 68 ms
9,216 KB |
testcase_24 | WA | - |
testcase_25 | AC | 130 ms
12,800 KB |
testcase_26 | AC | 37 ms
7,552 KB |
コンパイルメッセージ
warning: unused `Result` that must be used --> src/main.rs:240:9 | 240 | writeln!(out, "{}", alloc[i]+1); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | = note: this `Result` may be an `Err` variant, which should be handled = note: `#[warn(unused_must_use)]` on by default = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)
ソースコード
#[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();}}pub fn btree_pop<T:Ord+Clone>(set: &mut BTreeSet<T>) -> Option<T> {let ret : Option<T> = set.iter().next().map(|k| k.clone());if let Some(x) = &ret {set.remove(x);}ret}fn solve() {let out = stdout();let mut out = BufWriter::new(out.lock());input!{n:usize,k1:usize,k2:usize,q:usize,ab:[(i64,i64);q]}let mut tablecoord = vec![];for i in 0..n {let i = i as i64;tablecoord.push(i*3);}let k1 = k1-1;let k2 = k2-1;let doorcoord = if k1 > k2 {tablecoord[k1]-1} else {tablecoord[k1]+1};let mut tableadj = vec![vec![]; n];tableadj[0].push(1);for i in 1..n-1 {tableadj[i].push(i-1);tableadj[i].push(i+1);}tableadj[n-1].push(n-2);let mut tabledist = vec![0;n];for i in 0..n {tabledist[i] = i64::abs(tablecoord[i] - doorcoord);}let mut forbidcnt = vec![0; n];let mut waitq = VecDeque::new();let mut tablemain = BTreeSet::new();for i in 0..n {tablemain.insert((tabledist[i], i));}let mut tablesub = BTreeSet::new();let mut events = BinaryHeap::new();for i in 0..q {events.push((-1 * ab[i].0, false, i));}let mut alloc = vec![n; q];loop {if events.is_empty() { break; }let evt = events.pop().unwrap();let (t, b, man) = evt;let t = -1 * t;if b { // leavelet tbl = alloc[man];// 戻すlet x = (tabledist[tbl], tbl);if forbidcnt[tbl] == 0 {tablemain.insert(x);} else {tablesub.insert(x);}for &adj in &tableadj[tbl] {forbidcnt[adj] -= 1;if forbidcnt[adj] == 0 {let x = (tabledist[adj], adj);if tablesub.remove(&x) {tablemain.insert(x);}}}} else {// まず最初にウェイトキューに入れることにする// すでに待ってる人たちと同一に扱うためwaitq.push_back(man);}while !tablemain.is_empty() && !waitq.is_empty() {let (_, tbl) = btree_pop(&mut tablemain).unwrap();let man = waitq.pop_front().unwrap();alloc[man] = tbl;// 帰るイベントを登録する// 同時刻なら帰るイベントを優先するlet leave_t = t + ab[man].1;events.push((-1 * leave_t, true, man));for &adj in &tableadj[tbl] {if forbidcnt[adj] == 0 {let x = (tabledist[adj], adj);if tablemain.remove(&x) {tablesub.insert(x);}}forbidcnt[adj] += 1;}}while !tablesub.is_empty() && !waitq.is_empty() {let (_, tbl) = btree_pop(&mut tablesub).unwrap();let man = waitq.pop_front().unwrap();alloc[man] = tbl;// 帰るイベントを登録する// falseにすることで同時刻ならleaveを優先するlet leave_t = t + ab[man].1;events.push((-1 * leave_t, true, man));for &adj in &tableadj[tbl] {if forbidcnt[adj] == 0 {let x = (tabledist[adj], adj);if tablemain.remove(&x) {tablesub.insert(x);}}forbidcnt[adj] += 1;}}}for i in 0..q {writeln!(out, "{}", alloc[i]+1);}}