結果

問題 No.1959 Prefix MinMax
コンテスト
ユーザー cutmdo
提出日時 2022-05-31 04:03:41
言語 Rust
(1.83.0 + proconio)
結果
RE  
実行時間 -
コード長 5,136 bytes
コンパイル時間 13,936 ms
コンパイル使用メモリ 402,308 KB
実行使用メモリ 25,604 KB
平均クエリ数 4.00
最終ジャッジ日時 2024-09-21 01:03:08
合計ジャッジ時間 18,495 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

// use rand::seq::SliceRandom;
// use rand::Rng;

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(" ")
        );
        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(" ")
        );
    }
}
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] == 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).map(|x| x & 1).collect::<Vec<i64>>();
    let up = submitter.ask(vp);

    let vm = (0..n).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();
    println!("{}", t);
    for _ in 0..t {
        let n: i64 = readln();
        println!("{}", n);
        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