結果

問題 No.1959 Prefix MinMax
ユーザー cutmdocutmdo
提出日時 2022-05-31 04:18:27
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 5,216 bytes
コンパイル時間 13,833 ms
コンパイル使用メモリ 405,716 KB
実行使用メモリ 25,592 KB
平均クエリ数 26.72
最終ジャッジ日時 2024-09-21 01:03:47
合計ジャッジ時間 14,832 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 22 ms
24,836 KB
testcase_01 AC 21 ms
24,824 KB
testcase_02 AC 19 ms
24,836 KB
testcase_03 AC 20 ms
24,836 KB
testcase_04 AC 21 ms
25,220 KB
testcase_05 AC 20 ms
24,836 KB
testcase_06 AC 20 ms
25,220 KB
testcase_07 AC 32 ms
24,580 KB
testcase_08 AC 32 ms
24,964 KB
testcase_09 AC 33 ms
25,220 KB
testcase_10 AC 33 ms
25,220 KB
testcase_11 AC 31 ms
24,580 KB
testcase_12 AC 33 ms
24,836 KB
testcase_13 AC 33 ms
25,220 KB
testcase_14 AC 33 ms
25,112 KB
testcase_15 AC 31 ms
24,824 KB
testcase_16 AC 32 ms
24,964 KB
testcase_17 AC 33 ms
25,220 KB
testcase_18 AC 30 ms
25,220 KB
testcase_19 AC 31 ms
24,580 KB
testcase_20 AC 31 ms
24,836 KB
testcase_21 AC 32 ms
24,580 KB
testcase_22 AC 31 ms
24,568 KB
testcase_23 AC 32 ms
24,964 KB
testcase_24 AC 33 ms
25,348 KB
testcase_25 AC 32 ms
24,836 KB
testcase_26 AC 30 ms
24,580 KB
testcase_27 AC 32 ms
24,820 KB
testcase_28 AC 31 ms
25,220 KB
testcase_29 AC 31 ms
24,836 KB
testcase_30 AC 33 ms
25,076 KB
testcase_31 AC 32 ms
25,592 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `stdout`
 --> src/main.rs:3:15
  |
3 | use std::io::{stdout, Write};
  |               ^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

ソースコード

diff # 

// use rand::seq::SliceRandom;
// use rand::Rng;
use std::io::{stdout, Write};

fn get_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().to_string()
}
fn readln<T>() -> T
where
    T: std::str::FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    get_line().parse().unwrap()
}

trait Submitter {
    fn ask(&self, v: Vec<i64>) -> Vec<i64>;
    fn submit(&self, v: Vec<i64>);
}

struct JudgeSubmitter {}
struct LocalSubmitter {
    n: i64,
    p: Vec<i64>,
}

impl Submitter for JudgeSubmitter {
    fn ask(&self, v: Vec<i64>) -> Vec<i64> {
        println!(
            "? {}",
            v.iter()
                .map(|x| x.to_string())
                .collect::<Vec<String>>()
                .join(" ")
        );
        std::io::stdout().flush().unwrap();
        let ret: Vec<i64> = get_line()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect::<Vec<i64>>();
        return ret;
    }
    fn submit(&self, v: Vec<i64>) {
        println!(
            "! {}",
            v.iter()
                .map(|x| x.to_string())
                .collect::<Vec<String>>()
                .join(" ")
        );
        std::io::stdout().flush().unwrap();
    }
}
impl Submitter for LocalSubmitter {
    fn ask(&self, v: Vec<i64>) -> Vec<i64> {
        let mut ret = vec![self.p[0]; self.n as usize];
        for i in 1..self.n as usize {
            ret[i] = if v[i - 1] == 0 {
                std::cmp::min(ret[i - 1], self.p[i])
            } else {
                std::cmp::max(ret[i - 1], self.p[i])
            };
        }
        return ret;
    }
    fn submit(&self, p: Vec<i64>) {
        if p != self.p {
            println!("---- ERROR ----");
            println!("cor = {:?}\nyou = {:?}", self.p, p);
        }
    }
}

fn solve(n: i64, submitter: &dyn Submitter) {
    let mut ans = vec![-1; n as usize];
    let vp = (0..n - 1).map(|x| x & 1).collect::<Vec<i64>>();
    let up = submitter.ask(vp);

    let vm = (0..n - 1).map(|x| (x + 1) & 1).collect::<Vec<i64>>();
    let dw = submitter.ask(vm);

    let mut used = vec![false; n as usize];
    for i in 1..n as usize {
        if up[i - 1] != up[i] {
            ans[i] = up[i];
            used[ans[i] as usize - 1] = true
        }
        if dw[i - 1] != dw[i] {
            ans[i] = dw[i];
            used[ans[i] as usize - 1] = true
        }
    }

    let p = used.iter().enumerate().find(|(_, &b)| !b);
    if let Some(p) = p {
        ans[0] = p.0 as i64 + 1;
    }
    submitter.submit(ans);
}

fn main() {
    let t: i64 = readln();
    for _ in 0..t {
        let n: i64 = readln();
        let submitter: &dyn Submitter = &JudgeSubmitter {};
        solve(n, submitter)
    }
    /*
    for _ in 0..100 {
        let mut rng = rand::thread_rng();
        let n: i64 = rng.gen_range(1, 10);
        let mut p = (1..n + 1).collect::<Vec<i64>>();
        p.shuffle(&mut rng);
        let submitter: &dyn Submitter = &LocalSubmitter { n, p };
        solve(n, submitter);
    }
    */
}

/* ------------- 以下マクロ -------------*/
pub mod io_pro {
    #[macro_export]
    macro_rules!
        input{
        (sc=$sc:expr,$($r:tt)*)=>{
            input_inner!{$sc,$($r)*}
        };
        ($($r:tt)*)=>{
            let mut sc=io_pro::Scanner::new(std::io::stdin().lock());
            input_inner!{sc,$($r)*}
        };
    }

    #[macro_export]
    macro_rules! input_inner{
        ($sc:expr)=>{};
        ($sc:expr,)=>{};
        ($sc:expr,$var:ident:$t:tt$($r:tt)*)=>{
            let $var=read_value!($sc,$t);
            input_inner!{$sc $($r)*}
        };
        ($sc:expr,mut $var:ident:$t:tt$($r:tt)*)=>{
            let mut $var=read_value!($sc,$t);
            input_inner!{$sc $($r)*}
        };
    }

    #[macro_export]
    macro_rules! read_value{
        ($sc:expr,($($t:tt),*))=>{
            ($(read_value!($sc,$t)),*)
        };
        ($sc:expr,[$t:tt;$len:expr])=>{
            (0..$len).map(|_|read_value!($sc,$t)).collect::<Vec<_>>()
        };
        ($sc:expr,Chars)=>{read_value!($sc,String).chars().collect::<Vec<char>>()};
        ($sc:expr,Usize1)=>{read_value!($sc,usize)-1};
        ($sc:expr,$t:ty)=>{$sc.next::<$t>()};
    }
    pub struct Scanner {
        s: Box<str>,
        input: std::str::SplitAsciiWhitespace<'static>,
    }
    impl Scanner {
        pub fn new<R: std::io::Read>(mut reader: R) -> Self {
            let s = {
                let mut s = String::new();
                reader.read_to_string(&mut s).unwrap();
                s.into_boxed_str()
            };
            let mut sc = Scanner {
                s,
                input: "".split_ascii_whitespace(),
            };
            use std::mem;
            let s: &'static str = unsafe { mem::transmute(&*sc.s) };
            sc.input = s.split_ascii_whitespace();
            sc
        }
        #[inline]
        pub fn next<T: std::str::FromStr>(&mut self) -> T
        where
            T::Err: std::fmt::Debug,
        {
            self.input
                .next()
                .unwrap()
                .parse::<T>()
                .expect("Parse error")
        }
    }
}
0