結果

問題 No.594 壊れた宝物発見機
ユーザー phsplsphspls
提出日時 2020-07-01 23:06:22
言語 Rust
(1.77.0)
結果
AC  
実行時間 409 ms / 2,000 ms
コード長 4,434 bytes
コンパイル時間 1,074 ms
コンパイル使用メモリ 150,152 KB
実行使用メモリ 447,952 KB
平均クエリ数 179.65
最終ジャッジ日時 2023-09-24 03:43:54
合計ジャッジ時間 11,458 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 409 ms
447,456 KB
testcase_01 AC 394 ms
447,536 KB
testcase_02 AC 387 ms
447,488 KB
testcase_03 AC 394 ms
447,268 KB
testcase_04 AC 388 ms
447,436 KB
testcase_05 AC 387 ms
447,176 KB
testcase_06 AC 392 ms
447,464 KB
testcase_07 AC 386 ms
447,376 KB
testcase_08 AC 393 ms
447,360 KB
testcase_09 AC 387 ms
447,456 KB
testcase_10 AC 404 ms
447,380 KB
testcase_11 AC 385 ms
447,932 KB
testcase_12 AC 387 ms
447,456 KB
testcase_13 AC 390 ms
447,316 KB
testcase_14 AC 393 ms
447,592 KB
testcase_15 AC 388 ms
447,784 KB
testcase_16 AC 387 ms
447,640 KB
testcase_17 AC 390 ms
447,952 KB
testcase_18 AC 384 ms
447,260 KB
testcase_19 AC 387 ms
447,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn update(xyz: (usize, usize, usize), xyzd: &mut Vec<Vec<Vec<Option<usize>>>>) {
    let x = xyz.0;
    let y = xyz.1;
    let z = xyz.2;
    if xyzd[x][y][z].is_some() { return; }
    println!("? {} {} {}", x as isize - 150, y as isize - 150, z as isize - 150);
    let mut d = String::new();
    std::io::stdin().read_line(&mut d).ok();
    let d: usize = d.trim().parse().unwrap();
    xyzd[x][y][z] = Some(d);
}

fn get_coord(axis: usize, base: usize, a: usize, b: usize) -> (usize, usize, usize) {
    match axis {
        0 => (base, a, b),
        1 => (b, base, a),
        _ => (a, b, base)
    }
}

fn get_min_idx(points: &Vec<usize>, axis: usize, a: usize, b: usize, xyzd: &Vec<Vec<Vec<Option<usize>>>>) -> usize {
    let i0 = get_coord(axis, points[0], a, b);
    let i1 = get_coord(axis, points[1], a, b);
    let i2 = get_coord(axis, points[2], a, b);
    let i3 = get_coord(axis, points[3], a, b);
    if    xyzd[i0.0][i0.1][i0.2].unwrap() == xyzd[i1.0][i1.1][i1.2].unwrap()
       && xyzd[i0.0][i0.1][i0.2].unwrap() == xyzd[i2.0][i2.1][i2.2].unwrap()
       && xyzd[i0.0][i0.1][i0.2].unwrap() == xyzd[i3.0][i3.1][i3.2].unwrap()
    { return 4; }
    let temp = vec![
        (i0, xyzd[i0.0][i0.1][i0.2].unwrap())
      , (i1, xyzd[i1.0][i1.1][i1.2].unwrap())
      , (i2, xyzd[i2.0][i2.1][i2.2].unwrap())
      , (i3, xyzd[i3.0][i3.1][i3.2].unwrap())
    ];
    let temp = temp.iter().min_by_key(|pair| pair.1).unwrap().0;
    if temp == i0 { return 0; }
    else if temp == i1 { return 1; }
    else if temp == i2 { return 2; }
    else { return 3; }
}

fn fuzzy_detect(axis: usize, low_up: &mut Vec<Vec<usize>>, xyzd: &mut Vec<Vec<Vec<Option<usize>>>>) {
    let mut lower = low_up[axis][0];
    let mut upper = low_up[axis][1];
    let a = match axis {
        0 => (low_up[1][0] + low_up[1][1]) / 2,
        1 => (low_up[2][0] + low_up[2][1]) / 2,
        _ => (low_up[0][0] + low_up[0][1]) / 2
    };
    let b = match axis {
        0 => (low_up[2][0] + low_up[2][1]) / 2,
        1 => (low_up[0][0] + low_up[0][1]) / 2,
        _ => (low_up[1][0] + low_up[1][1]) / 2
    };
    update(get_coord(axis, lower, a, b), xyzd);
    update(get_coord(axis, upper, a, b), xyzd);
    while upper - lower > 4 {
        let lmiddle: usize = (lower * 2 + upper) / 3;
        let rmiddle: usize = (lower + upper * 2) / 3;
        update(get_coord(axis, lmiddle, a, b), xyzd);
        update(get_coord(axis, rmiddle, a, b), xyzd);
        let min_idx = get_min_idx(&vec![lower, lmiddle, rmiddle, upper], axis, a, b, xyzd);
        match min_idx {
            0 => { upper = lmiddle; match axis { 0 => {low_up[0][1] = lmiddle;}, 1 => {low_up[1][1] = lmiddle;}, _ => {low_up[2][1] = lmiddle;}}; },
            1 => { upper = rmiddle; match axis { 0 => {low_up[0][1] = rmiddle;}, 1 => {low_up[1][1] = rmiddle;}, _ => {low_up[2][1] = rmiddle;}}; },
            2 => { lower = lmiddle; match axis { 0 => {low_up[0][0] = lmiddle;}, 1 => {low_up[1][0] = lmiddle;}, _ => {low_up[2][0] = lmiddle;}}; },
            3 => { lower = rmiddle; match axis { 0 => {low_up[0][0] = rmiddle;}, 1 => {low_up[1][0] = rmiddle;}, _ => {low_up[2][0] = rmiddle;}}; },
            _ => { break; }
        }
    }
}

fn main() {
    let mut xyzd: Vec<Vec<Vec<Option<usize>>>> = vec![vec![vec![None; 301]; 301]; 301];
    //x, y, z
    let mut low_up: Vec<Vec<usize>> = vec![vec![0, 300]; 3];
    let mut prev = low_up.clone();
    loop {
        fuzzy_detect(0, &mut low_up, &mut xyzd);
        fuzzy_detect(1, &mut low_up, &mut xyzd);
        fuzzy_detect(2, &mut low_up, &mut xyzd);
        if prev.iter().zip(low_up.iter()).filter(|pair| pair.0[0] == pair.1[0] && pair.0[1] == pair.1[1]).count() == 3 {
            break;
        }
        prev = low_up.clone();
    }
    let mut result: Option<(usize, usize, usize, usize)> = None;
    for x in low_up[0][0]..=low_up[0][1] {
        for y in low_up[1][0]..=low_up[1][1] {
            for z in low_up[2][0]..=low_up[2][1] {
                update((x, y, z), &mut xyzd);
                if result.is_none() {
                    result = Some((x, y, z, xyzd[x][y][z].unwrap()));
                } else if result.unwrap().3 > xyzd[x][y][z].unwrap() {
                    result = Some((x, y, z, xyzd[x][y][z].unwrap()));
                }
            }
        }
    }
    println!("! {} {} {}", result.unwrap().0 as isize - 150, result.unwrap().1 as isize - 150, result.unwrap().2 as isize - 150);
}
0