結果
問題 | No.2978 Lexicographically Smallest and Largest Subarray |
ユーザー |
|
提出日時 | 2024-12-14 15:05:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 207 ms / 2,000 ms |
コード長 | 2,486 bytes |
コンパイル時間 | 13,164 ms |
コンパイル使用メモリ | 402,344 KB |
実行使用メモリ | 25,220 KB |
平均クエリ数 | 1499.00 |
最終ジャッジ日時 | 2024-12-14 15:05:58 |
合計ジャッジ時間 | 27,507 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 57 |
ソースコード
#![allow(unused_imports, non_snake_case)] use proconio::{marker::*, *}; fn main() { input_interactive! { N: usize, _Q: usize, } // すべてのsuffixをmin_max_elementのように3N/2回のクエリでmin/maxを求める let (min_cands, max_cands) = { let mut min_cands = Vec::with_capacity(N / 2); let mut max_cands = Vec::with_capacity(N / 2); for i in 0..N/2 { // i*2,i*2+1 if ask(i*2, N - 1, i*2+1, N - 1) { min_cands.push(i*2); max_cands.push(i*2+1); } else { min_cands.push(i*2+1); max_cands.push(i*2); } } (min_cands, max_cands) }; let min_suffix = { let mut cur_min = min_cands[0]; for &i in &min_cands[1..] { if ask(i, N - 1, cur_min, N - 1) { cur_min = i; } } cur_min }; let max_suffix = { let mut cur_max = max_cands[0]; for &i in &max_cands[1..] { if ask(cur_max, N - 1, i, N - 1) { cur_max = i; } } cur_max }; println!("! {} {} {} {}", min_suffix + 1, min_suffix + 1, max_suffix + 1, N); } /// A[l1..=r1] < A[l2..=r2] を返す fn ask(l1: usize, r1: usize, l2: usize, r2: usize) -> bool { use std::io::{stdout, Write}; println!("? {} {} {} {}", l1 + 1, r1 + 1, l2 + 1, r2 + 1); stdout().flush().unwrap(); input_interactive! { res: i8, } match res { 0 => false, 1 => true, -1 => panic!("invalid query"), _ => unreachable!(), } } #[macro_export] macro_rules! mat { ($($e:expr),*) => { vec![$($e),*] }; ($($e:expr,)*) => { vec![$($e),*] }; ($e:expr; $d:expr) => { vec![$e; $d] }; ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] }; } #[macro_export] macro_rules! chmin { ($a:expr, $b:expr) => { if $a > $b { $a = $b; true } else { false } }; } #[macro_export] macro_rules! chmax { ($a:expr, $b:expr) => { if $a < $b { $a = $b; true } else { false } }; } /// https://maguro.dev/debug-macro/ #[macro_export] macro_rules! debug { ($($a:expr),* $(,)*) => { #[cfg(debug_assertions)] eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*); }; }