AtCoder Beginner Contest 299 D

https://atcoder.jp/contests/abc299/tasks/abc299_d

最初が0で最後が1と決まっているのがポイントですね。あとは二分探索で。

// Find by Query
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

fn get_char(pos: i32) -> i32 {
    println!("? {}", pos);
    read()
}

fn bin_search(pos1: i32, pos2: i32, chr1: i32) -> i32 {
    if pos2 - pos1 == 1 {
        pos1
    }
    else {
        let mid = (pos1 + pos2) / 2;
        let chr_mid = get_char(mid);
        if chr_mid != chr1 {
            bin_search(pos1, mid, chr1)
        }
        else {
            bin_search(mid, pos2, chr_mid)
        }
    }
}

fn main() {
    let N: i32 = read();
    println!("! {}", bin_search(1, N, 0));
}