Submission #55886383

---

Source Code Expand

use interval_search_for_interactive_problem::{FibonacciSearch, QueryProcesser};
use proconio::{input, source::auto::AutoSource};
use std::io::BufRead;

fn main() {
    let t = read();
    for _ in 0..t {
        solve();
    }
}

fn solve() {
    let n = read();
    let q = QueryProcesser::new();
    let eval_fn = |x, y| x > y;
    let mut solver = FibonacciSearch::new(1, n);
    let ans = solver.solve(q, eval_fn);
    println!("! {ans}");
}

fn read() -> i64 {
    let mut s = "".to_string();
    let stdin = std::io::stdin();
    let mut handle = stdin.lock();
    handle.read_line(&mut s).unwrap();
    let source = AutoSource::from(s.as_str());
    input! {
        from source,
        res: i64,
    }
    res
}

mod interval_search_for_interactive_problem {
    use std::collections::HashMap;

    use crate::read;

    type Output = i64;

    pub struct QueryProcesser {
        pub map: HashMap<i64, Output>,
    }
    impl QueryProcesser {
        pub fn new() -> Self {
            Self {
                map: HashMap::new(),
            }
        }
        fn query(&mut self, i: i64) -> Output {
            if let Some(&x) = self.map.get(&i) {
                x
            } else {
                println!("? {i}");
                let x = read();
                self.map.insert(i, x);
                x
            }
        }
    }

    pub struct FibonacciSearch {
        ml: i64,     // ng_min から分割点の左までの長さ
        mr: i64,     // ng_min から分割点の右までの長さ
        ng_min: i64, // 定義域の最小値 - 1
        ng_max: i64, // 定義域の最大値 + 1
    }

    impl FibonacciSearch {
        /// low: 定義域の最小値
        /// high: 定義域の最大値
        pub fn new(low: i64, high: i64) -> Self {
            Self::build(low, high)
        }

        fn build(low: i64, high: i64) -> Self {
            let (ng_min, ng_max) = (low - 1, high + 1);
            let (mut ml, mut mr) = (1, 1);

            // 探索区間の長さ以上となる最小のフィボナッチ数を求める
            while ml + mr < ng_max - ng_min {
                ml += mr;
                std::mem::swap(&mut ml, &mut mr);
            }

            Self {
                ml,
                mr,
                ng_min,
                ng_max,
            }
        }

        /// eval_fn: eval_fn(x, y) に対して x の方が評価が高いとき true, そうでないとき false を返すclosure
        pub fn solve<F>(&mut self, mut f: QueryProcesser, eval_fn: F) -> Output
        where
            F: Fn(Output, Output) -> bool,
        {
            let mut lval = f.query(self.ng_min + self.ml);
            let mut rval = f.query(self.ng_min + self.mr);

            while self.ml < self.mr {
                self.shrink_interval();

                if eval_fn(lval, rval) {
                    rval = lval;
                    lval = f.query(self.ng_min + self.ml);
                } else {
                    self.ng_min += self.mr;
                    if self.ng_min + self.mr < self.ng_max {
                        lval = rval;
                        rval = f.query(self.ng_min + self.mr);
                    } else {
                        self.shrink_interval();
                        lval = f.query(self.ng_min + self.ml);
                    }
                }
            }

            if eval_fn(lval, rval) {
                lval
            } else {
                rval
            }
        }

        fn shrink_interval(&mut self) {
            self.mr -= self.ml;
            std::mem::swap(&mut self.ml, &mut self.mr);
        }
    }
}

Submission Info

Judge Result